STL Containers

The Standard Template Library (STL) provides robust, efficient containers. Knowing which one to use is key to writing high-performance C++.

Sequence Containers

std::vector (The Default Choice)

A dynamic array that grows automatically. - Access: O(1) - Insert at end: Amortized O(1) - Insert in middle: O(n)

#include <vector>

std::vector<int> numbers = {1, 2, 3};
numbers.push_back(4); // Add to end

std::array (Fixed Size)

A thin wrapper around C-style arrays. Allocated on the stack (usually). - Size: Fixed at compile-time. - Performance: Zero overhead.

#include <array>

std::array<int, 3> point = {10, 20, 30};

std::string

A specialized container for text. - Small String Optimization (SSO): Short strings are stored directly in the object, avoiding heap allocation.

Associative Containers

std::map vs std::unordered_map

Feature	std::map	std::unordered_map
Implementation	Balanced Binary Tree (Red-Black)	Hash Table
Order	Sorted by Key	Undefined
Search Time	O(log n)	O(1) Average

#include <map>
std::map<std::string, int> scores;
scores["Alice"] = 100;
scores["Bob"] = 90;
// Iterating prints Alice then Bob (Alphabetical)

std::set and std::unordered_set

Similar to maps, but store unique keys only.

Pairs and Tuples

Utilities to bundle multiple values.

std::pair

Holds two values.

std::pair<int, std::string> p = {1, "Apple"};
std::cout << p.first << ": " << p.second;

std::tuple

Holds N values.

#include <tuple>
std::tuple<int, double, std::string> t = {1, 3.14, "Pi"};
std::cout << std::get<0>(t); // 1

Iterators

Iterators are objects that point to elements in a container. They generalize pointers.

• begin(): Points to the first element.
• end(): Points past the last element.

std::vector<int> v = {10, 20, 30};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

Modern Views (Non-owning)

These are lightweight objects that refer to data owned by other containers. They prevent unnecessary copies.

std::string_view (C++17)

A read-only view of a string (or part of it).

void print_prefix(std::string_view str) {
    // No copy is made, even if passed a long std::string or char*
    std::cout << str.substr(0, 3);
}

std::span (C++20)

A view of a contiguous sequence of objects (like an array or vector).

#include <span>

void process_buffer(std::span<uint8_t> buffer) {
    for (auto& byte : buffer) {
        byte ^= 0xFF; // Invert bits
    }
}

uint8_t raw_data[1024];
std::vector<uint8_t> vec_data(500);

process_buffer(raw_data); // Works!
process_buffer(vec_data); // Works!

Container Adapters

• std::stack: LIFO (Last In, First Out).
• std::queue: FIFO (First In, First Out).
• std::priority_queue: Elements are popped in priority order (default: largest first).