Stl_containers

STL Containers Overview

The Standard Template Library (STL) provides a collection of container classes that store and manage data efficiently. This chapter gives you an overview of all the STL containers and their use cases.

What is STL?

The STL is a powerful library included with C++ that provides:

┌─────────────────────────────────────────────────────────────┐
│                  STL Components                             │
├─────────────────────────────────────────────────────────────┤
│  Containers   →  Data structures to store elements          │
│  Algorithms   →  Functions to manipulate container data     │
│  Iterators   →  Objects to traverse container elements    │
│  Functors    →  Objects that can be called like functions  │
│  Allocators   →  Memory management for containers          │
└─────────────────────────────────────────────────────────────┘

Container Categories

┌─────────────────────────────────────────────────────────────┐
│                    STL Container Categories                  │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Sequence Containers      Associative Containers           │
│  ┌──────────────┐         ┌──────────────────┐             │
│  │ vector       │         │ set             │              │
│  │ deque        │         │ │              │
│  │ list         │         │ map multiset                    │              │
│  │ forward_list │         │ multimap        │              │
│  │ array        │         │ unordered_set   │              │
│  │ string       │         │ unordered_map   │              │
│  └──────────────┘         │ unordered_multiset             │
│                           │ unordered_multimap            │
│                           └──────────────────┘             │
│  Container Adapters                                              │
│  ┌──────────────┐                                            │
│  │ stack       │                                            │
│  │ queue       │                                            │
│  │ priority_queue                                            │
│  └──────────────┘                                            │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Sequence Containers

Store elements in a linear sequence.

std::vector

Dynamic array with random access:

• Fast insert/delete at the end
• Slow insert/delete in the middle
• Fast random access
• Contiguous memory

#include <vector>

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6);
vec.pop_back();
int first = vec[0];
int last = vec.back();

std::deque

Double-ended queue:

• Fast insert/delete at both ends
• Fast random access
• No contiguous guarantee

#include <deque>

std::deque<int> dq = {1, 2, 3};
dq.push_front(0);   // Add at front
dq.push_back(4);    // Add at back

std::list

Doubly-linked list:

• Fast insert/delete anywhere
• No random access
• Bidirectional iteration only

#include <list>

std::list<int> lst = {1, 2, 3};
lst.push_back(4);
lst.push_front(0);
// lst.insert(++lst.begin(), 5);

std::forward_list

Singly-linked list (C++11):

• Like list but one direction
• More memory efficient than list

std::array

Fixed-size array (C++11):

• Stack-allocated
• Fixed size known at compile time

#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};

Associative Containers

Store elements in sorted order, optimized for lookup.

std::set / std::multiset

• Unique elements / Multiple elements
• Sorted by key
• Fast lookup (O(log n))

#include <set>

std::set<int> s = {5, 2, 8, 1, 9};
s.insert(3);
bool found = s.count(5);
auto it = s.find(2);

std::map / std::multimap

Key-value pairs:

• Unique keys / Multiple keys
• Sorted by key
• Fast lookup (O(log n))

#include <map>

std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
int aliceAge = ages["Alice"];

for (const auto& [name, age] : ages) {
    std::cout << name << ": " << age << "\n";
}

Unordered Associative Containers (C++11)

Hash table implementation:

• O(1) average lookup
• No sorting guaranteed

#include <unordered_map>

std::unordered_map<std::string, int> hashMap;
hashMap["key"] = value;

// Faster for large datasets
// No ordering guaranteed

Container Adapters

Provide restricted interfaces:

std::stack

LIFO (Last In, First Out):

#include <stack>

std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
    std::cout << s.top() << " ";  // 3, 2, 1
    s.pop();
}

std::queue

FIFO (First In, First Out):

#include <queue>

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
    std::cout << q.front() << " ";  // 1, 2, 3
    q.pop();
}

std::priority_queue

Elements sorted by priority:

#include <queue>

std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
// Outputs: 5, 3, 1 (largest first)

Choosing the Right Container

Use Case	Recommended Container
General purpose, random access	std::vector
Add/remove at both ends	std::deque
Frequent insertion in middle	std::list
Sorted unique elements	std::set
Key-value lookup	std::map
Fast lookup, no ordering	std::unordered_map
LIFO stack	std::stack
FIFO queue	std::queue

Common Container Methods

// Size operations
container.size();     // Number of elements
container.empty();    // Check if empty

// Element access
container.front();    // First element
container.back();     // Last element
container.at(index);  // Bounds-checked access

// Iterators
container.begin();    // First element
container.end();      // Past last

// Modifiers
container.clear();    // Remove all
container.erase(it);  // Remove element(s)
container.insert(val);// Insert element
container.push_back(val);  // Add to end

Complete Example

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

int main() {
    // Vector - dynamic array
    std::vector<std::string> words = {"apple", "banana", "cherry"};
    words.push_back("date");

    std::cout << "=== Vector ===\n";
    for (const auto& w : words) {
        std::cout << w << " ";
    }
    std::cout << "\n";

    // Map - key-value store
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;

    std::cout << "\n=== Map ===\n";
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }

    // Set - unique sorted elements
    std::set<int> numbers = {5, 2, 8, 2, 1, 9, 5};

    std::cout << "\n=== Set (unique, sorted) ===\n";
    for (int n : numbers) {
        std::cout << n << " ";  // 1 2 5 8 9
    }
    std::cout << "\n";

    // Algorithm with vector
    std::vector<int> nums = {5, 2, 8, 1, 9, 3};
    std::sort(nums.begin(), nums.end());

    std::cout << "\n=== Sorted Vector ===\n";
    for (int n : nums) {
        std::cout << n << " ";  // 1 2 3 5 8 9
    }
    std::cout << "\n";

    return 0;
}

Key Takeaways

• STL provides efficient, tested container implementations
• Choose container based on access patterns
• std::vector is the default choice for most cases
• Use std::map for key-value lookups with ordering
• Use std::unordered_map for fast O(1) lookups
• Container adapters provide restricted interfaces (stack, queue)

Next Steps

Let’s dive deeper into vectors and strings.

Next Chapter: 15_vectors_strings.md - Vectors and Strings