STL Containers

The Standard Template Library (STL) offers a suite of highly optimized container templates. Choosing the correct container for a given workload is essential for maximizing performance, especially on resource-constrained platforms like the Raspberry Pi.

---

1. Sequence Containers

Sequence containers store elements in a linear arrangement.

  std::vector / std::array (Contiguous Memory Layout)
  ┌───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 2 │ 3 │ 4 │  ◄── Quick random access (index)
  └───┴───┴───┴───┴───┘

  std::list (Non-Contiguous Link Nodes)
  ┌────┐     ┌────┐     ┌────┐
  │Node│ ──> │Node│ ──> │Node│  ◄── Slow index access (must traverse list)
  └────┘     └────┘     └────┘

1. std::vector<T> (The Default Standard)

std::vector represents a dynamic array. Elements are stored in contiguous memory blocks. - Random Access: $O(1)$ constant time. - Insertion at end: Amortized $O(1)$. - Insertion in middle: $O(n)$ linear time (since elements must be shifted in memory).

Capacity vs. Size and the reserve() Optimization

When a vector's size exceeds its allocated memory (capacity), it allocates a new, larger memory block (usually $1.5\times$ or $2\times$ the old size), copies the existing elements to the new block, and deletes the old block. This is a very expensive operation.

If you know the approximate number of elements beforehand, use .reserve() to pre-allocate memory and prevent redundant reallocations:

#include <vector>

void fill_vector() {
    std::vector<int> vec;
    vec.reserve(10000); // Allocates memory for 10,000 items in one call

    for (int i = 0; i < 10000; ++i) {
        vec.push_back(i); // Zero reallocations!
    }
}

2. std::array<T, N> (Fixed-Size Stack Allocation)

std::array is a safe, modern wrapper around raw C-style arrays. Its size must be known at compile time. - Overhead: Zero runtime overhead compared to raw arrays. - Safety: Supports .at(index) which performs bound checking (throwing std::out_of_range on failure).

#include <array>

std::array<int, 3> coords{10, 20, 30};
int val = coords.at(2); // Bound-checked access

3. std::list<T> (Doubly-Linked List)

std::list allocates memory for elements as individual, non-contiguous nodes. - Insertion/Deletion: $O(1)$ anywhere in the list (once the node is located). - Access: $O(n)$ search (no index access, must traverse node pointers). - Cache Misses: High. Contiguous memory containers like std::vector perform significantly better on modern CPUs because of CPU cache lines.

---

2. Associative & Unordered Containers

Associative containers store key-value pairs or unique keys, optimized for fast lookup.

Container	Implementation	Key Sorting	Search Complexity	Typical Use Case
std::map	Balanced Binary Tree (Red-Black)	Yes (Sorted)	$O(\log n)$	When keys must be sorted
std::unordered_map	Hash Table	No (Arbitrary)	$O(1)$ Average / $O(n)$ Worst	Fast dictionary lookups
std::set	Balanced Binary Tree	Yes	$O(\log n)$	Maintaining unique sorted keys
std::unordered_set	Hash Table	No	$O(1)$ Average	Fast uniqueness checks

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>

int main() {
    // 1. std::map: Sorted order
    std::map<std::string, int> ages;
    ages["Charlie"] = 30;
    ages["Alice"] = 25;

    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n"; 
        // Output is sorted: Alice then Charlie
    }

    // 2. std::unordered_map: Unsorted, fast lookups
    std::unordered_map<int, std::string> error_codes;
    error_codes[404] = "Not Found";
    error_codes[200] = "OK";

    return 0;
}

---

3. Iterators

Iterators behave like generalized pointers, allowing you to traverse different container types using a unified syntax.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {10, 20, 30};

    // Forward iterator traversal
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        std::cout << *it << " "; // Dereference iterator
    }
    std::cout << "\n";

    // Constant iterator (Read-only)
    std::vector<int>::const_iterator cit = nums.cbegin();

    // Reverse iterator (Traverse backwards)
    for (auto rit = nums.rbegin(); rit != nums.rend(); ++rit) {
        std::cout << *rit << " "; // Prints: 30 20 10
    }
    std::cout << "\n";
}

---

4. Modern Non-Owning Views: Zero-Copy Views

Modern C++ provides lightweight, non-owning reference templates that point to existing memory buffers. This avoids expensive copying and allocates no heap memory.

1. std::string_view (C++17)

Provides a read-only view of a contiguous character sequence (works with std::string or const char*).

#include <string_view>
#include <iostream>
#include <string>

// String parameter: no copy is triggered, regardless of string size
void log_message(std::string_view message) {
    std::cout << "Log: " << message << "\n";
}

int main() {
    std::string dynamic_str = "Heap allocated string";
    log_message(dynamic_str);        // View of std::string
    log_message("Literal string");    // View of raw literal (zero heap allocation)
}

2. std::span (C++20)

Provides a view of a contiguous block of objects. It can wrap a raw C-style array, a std::vector, or a std::array without making a copy.

#include <span>
#include <vector>
#include <array>
#include <iostream>

// Accepts any contiguous buffer containing integers
void invert_buffer(std::span<int> data) {
    for (int& val : data) {
        val = -val;
    }
}

int main() {
    int raw_arr[] = {1, 2, 3};
    std::vector<int> vec = {4, 5, 6};
    std::array<int, 3> arr = {7, 8, 9};

    invert_buffer(raw_arr); // Works!
    invert_buffer(vec);     // Works!
    invert_buffer(arr);     // Works!

    return 0;
}

---

Related Guides

• Templates — How STL containers are built using generic blueprints.
• STL Algorithms — Iterating and manipulating data inside STL containers.