C++ STL: Containers, Algorithms, and Iterators

C/C++ C/C++ 8 min read 1503 words Beginner ExcellentWiki Editorial Team

The C++ Standard Template Library (STL) is a collection of generic containers, algorithms, and iterators. It is the standard library’s most influential part — designed by Alexander Stepanov in the 1990s, it separates data structures from algorithms using iterators as a glue layer. Understanding the STL is essential for writing idiomatic, efficient C++.

This guide covers the most commonly used STL components with practical examples.

Containers

Sequence Containers

#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>

// vector — dynamic array, contiguous memory
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6);            // O(1) amortized
vec.pop_back();              // O(1)
vec.insert(vec.begin() + 2, 99);  // O(n)
vec.erase(vec.begin());      // O(n)
vec[3] = 42;                 // O(1) random access

// deque — double-ended queue
std::deque<int> deq = {1, 2, 3};
deq.push_front(0);           // O(1)
deq.push_back(4);            // O(1)
deq.pop_front();             // O(1)

// list — doubly-linked list
std::list<int> lst = {1, 2, 3};
lst.push_front(0);
lst.push_back(4);
lst.insert(++lst.begin(), 99);  // O(1) at iterator position

// array — fixed-size, stack-allocated
std::array<int, 5> arr = {10, 20, 30, 40, 50};
// arr.size() == 5, no dynamic allocation

Associative Containers

#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

// set — ordered, unique keys (usually red-black tree)
std::set<int> s = {3, 1, 4, 1, 5, 9};  // {1, 3, 4, 5, 9}
s.insert(2);
s.erase(1);
bool exists = s.contains(4);  // C++20

// map — ordered key-value pairs
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
// ages is ordered alphabetically by key

// unordered_set — hash table, O(1) average
std::unordered_set<int> us = {3, 1, 4, 1, 5};

// unordered_map — hash table key-value
std::unordered_map<std::string, int> scores;
scores["player1"] = 100;
scores["player2"] = 85;

Container Adaptors

#include <stack>
#include <queue>

// stack — LIFO
std::stack<int> st;
st.push(1);
st.push(2);
st.top();    // 2
st.pop();    // removes 2

// queue — FIFO
std::queue<int> q;
q.push(1);
q.push(2);
q.front();   // 1
q.back();    // 2
q.pop();     // removes 1

// priority_queue — max-heap by default
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
pq.top();    // 5

Iterators

Iterators bridge containers and algorithms. They come in different categories:

#include <iterator>

std::vector<int> vec = {10, 20, 30, 40, 50};

// Basic iteration
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << ' ';
---

// Range-based for (uses iterators internally)
for (const auto& v : vec) {
    std::cout << v << ' ';
---

// Iterator categories
auto it = vec.begin();
++it;          // Forward iterator (all containers)
--it;          // Bidirectional (list, set, map)
it += 3;       // Random access (vector, deque, array)
auto diff = it - vec.begin();  // Distance (random access)

// Reverse iteration
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    std::cout << *it << ' ';  // 50, 40, 30, 20, 10
---

// Iterator utilities
std::advance(it, 2);          // Advance by n
auto dist = std::distance(vec.begin(), it);  // Distance between iterators

Algorithms

#include <algorithm>
#include <numeric>

std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};

// Sorting
std::sort(v.begin(), v.end());               // {1, 2, 3, 4, 5, 6, 7, 8, 9}
std::partial_sort(v.begin(), v.begin() + 3, v.end());  // Top 3 sorted

// Searching
auto it = std::find(v.begin(), v.end(), 5);
bool exists = std::binary_search(v.begin(), v.end(), 5);  // Requires sorted range

// Modifying
std::fill(v.begin(), v.end(), 0);            // Set all to 0
std::transform(v.begin(), v.end(), v.begin(),
               [](int x) { return x * 2; }); // Double each element

// Removing
auto new_end = std::remove(v.begin(), v.end(), 0);
v.erase(new_end, v.end());                   // Erase-remove idiom

// Min/Max
auto [min_it, max_it] = std::minmax_element(v.begin(), v.end());

// Counting
int count = std::count(v.begin(), v.end(), 5);

// Numeric algorithms (in <numeric>)
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());
std::vector<int> diffs;
std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diffs));

Common Patterns

Erase-Remove Idiom

// Remove all elements matching a value
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
vec.erase(
    std::remove(vec.begin(), vec.end(), 2),
    vec.end()
);
// vec == {1, 3, 4, 5}

// Remove elements satisfying a predicate
vec.erase(
    std::remove_if(vec.begin(), vec.end(),
                   [](int x) { return x % 2 == 0; }),
    vec.end()
);

Custom Comparators

struct Person {
    std::string name;
    int age;
---;

// Sort by age descending, then name ascending
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age > b.age;
        return a.name < b.name;
    });

// Custom set with comparator
auto cmp = [](const Person& a, const Person& b) {
    return a.name < b.name;
---;
std::set<Person, decltype(cmp)> person_set(cmp);

Efficient Insertion

std::map<std::string, int> scores;

// Insert only if key doesn't exist
auto [it, inserted] = scores.try_emplace("Alice", 100);
if (inserted) {
    std::cout << "Inserted new entry\n";
---

// Get or insert default
int& score = scores["Bob"];  // Creates with 0 if not exists

// Insert with hint (for ordered containers)
auto hint = scores.lower_bound("Charlie");
scores.emplace_hint(hint, "Charlie", 50);

Performance Considerations

Container Selection Guide

Choosing the right container is critical for performance. Each STL container makes different trade-offs:

FAQ

What is the difference between malloc and new in C++? malloc allocates raw memory without calling constructors; new allocates memory and calls the constructor. In C++, prefer new for objects. free vs delete follows the same pattern — delete calls the destructor.

How do I prevent memory leaks in C/C++? Use RAII (Resource Acquisition Is Initialization) in C++ — smart pointers like std::unique_ptr and std::shared_ptr automatically free memory. In C, always pair every malloc with a free and use tools like Valgrind or AddressSanitizer to detect leaks.

What is undefined behavior in C/C++? Undefined behavior occurs when code performs operations that the language standard does not define — dereferencing a null pointer, buffer overflow, signed integer overflow. The compiler may generate any code, including unexpected results or crashes.

Should I learn C or C++ first? Learn C first if you want to understand low-level memory and system programming. Learn C++ first if you want object-oriented features and the STL. Both are valuable; C++ builds on C concepts.

What is the difference between a header file and a source file? Header files (.h) declare interfaces — function prototypes, class definitions, macros. Source files (.c or .cpp) implement the declarations. Headers are #included; source files are compiled separately and linked.

Iterators and Ranges

STL iterators provide a uniform interface for traversing containers. C++20 ranges simplify iteration further:

std::vector<int> v = {1, 2, 3, 4, 5};

// Traditional iterators
for (auto it = v.begin(); it != v.end(); ++it) { }

// Range-based for loop
for (int x : v) { }

// C++20 ranges
auto even = v | std::views::filter([](int x) { return x % 2 == 0; });
for (int x : even) { }

Algorithms Library

The <algorithm> header provides generic algorithms that operate on iterators. These are more expressive and less error-prone than hand-written loops:

std::vector<int> data = {5, 2, 8, 1, 9, 3};
std::sort(data.begin(), data.end());           // Sort
auto it = std::lower_bound(data.begin(),       // Binary search
    data.end(), 5);
std::transform(data.begin(), data.end(),        // Apply function
    data.begin(), [](int x) { return x * 2; });

Allocators

Allocators manage memory for containers. The default std::allocator uses new and delete. Custom allocators enable pool allocation, arena allocation, and NUMA-aware memory management for specialized use cases.

string_view and span

C++17 introduced std::string_view (non-owning string reference) and C++20 added std::span (non-owning contiguous sequence view). These types eliminate copies when passing read-only references to strings and arrays:

void parse(std::string_view sv) {
    // No copy — sv points to the original string
---
std::string s = "hello";
parse(s);  // Implicit conversion, no allocation

———–|——–|——-|——|—————| | vector | O(n) | O(n) | O(n) | O(1) | | deque | O(1)* | O(n) | O(n) | O(1) | | list | O(1) | O(1) | O(n) | O(n) | | set/map | O(log n) | O(log n) | O(log n) | — | | unordered_set/map | O(1) avg | O(1) avg | O(1) avg | — |

Use vector by default — it’s cache-friendly and fast
Use unordered_map for key-value lookups (hash table)
Use set/map when you need ordering
Use list only when you need O(1) insert/erase at arbitrary positions

Conclusion

The STL is the foundation of modern C++. Master vector, unordered_map, and set as your go-to containers. Learn the algorithm functions — sort, find, transform, accumulate — they eliminate loops and make your code clearer. Use iterators to bridge containers and algorithms, and always prefer STL algorithms over handwritten loops.

Related: Check our C++ OOP guide.

For a comprehensive overview, read our article on C File Io Guide.

Share this article

X LinkedIn Facebook Email