C++ Standard Library Containers — Complete Guide

The C++ Standard Library provides a family of type-safe, generic containers for storing collections of related objects. Each container is a class template parameterized on the element type, so a std::vector<int> and a std::vector<std::string> are distinct types sharing the same implementation. Containers manage their own memory, support range-based for loops through iterators, and integrate seamlessly with the standard algorithms in <algorithm> and <numeric>.

When in doubt about which container to use, start with std::vector. It stores elements contiguously in memory, offers O(1) random access and amortized O(1) push-back, and has the best cache locality of any sequence container.

Container Categories

The Standard Library divides containers into three main families:

Sequence Containers

Maintain the insertion order you specify: vector, deque, list, forward_list, array.

Associative Containers

Keep elements in sorted order by key: map, set, multimap, multiset.

Unordered Containers

Hash-based O(1) average lookup: unordered_map, unordered_set, unordered_multimap, unordered_multiset.

Sequence Containers

Sequence containers store elements in a linear arrangement and preserve the order in which you insert them.

`std::vector` — Dynamic Array

vector is the go-to sequence container. It allocates contiguous memory, supports O(1) random access via index, and grows automatically as elements are added. Iterators, pointers, and references are invalidated after any reallocation.

#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
    // Construction with initializer list
    std::vector<int> v = {5, 3, 1, 4, 2};

    // Append elements
    v.push_back(6);
    v.emplace_back(7);   // constructs in-place — more efficient for complex types

    // Random access
    std::cout << "First: " << v.front() << "\n";   // 5
    std::cout << "Last:  " << v.back()  << "\n";   // 7
    std::cout << "v[2]:  " << v[2]      << "\n";   // 1

    // Size and capacity
    std::cout << "size=" << v.size() << " capacity=" << v.capacity() << "\n";

    // Reserve avoids repeated reallocations
    v.reserve(100);

    // Range-based for loop
    for (int x : v)
        std::cout << x << ' ';
    std::cout << "\n";

    // Sort in place
    std::sort(v.begin(), v.end());

    // Erase element at index 2
    v.erase(v.begin() + 2);

    // Remove all elements
    v.clear();
    std::cout << "empty: " << std::boolalpha << v.empty() << "\n"; // true
}

`std::array` — Fixed-Size Array

array wraps a C-style array in a class template while preserving its fixed-size, stack-allocated nature. Unlike vector, the size is part of the type.

#include <array>
#include <algorithm>
#include <iostream>

int main()
{
    std::array<int, 5> a = {3, 1, 4, 1, 5};
    std::sort(a.begin(), a.end());

    for (int x : a)
        std::cout << x << ' '; // 1 1 3 4 5
    std::cout << "\n";

    std::cout << "size: " << a.size() << "\n"; // always 5
}

`std::deque` — Double-Ended Queue

deque offers O(1) insertions and removals at both ends, with O(1) random access. It does not store elements contiguously.

#include <deque>
#include <iostream>

int main()
{
    std::deque<int> dq = {2, 3, 4};
    dq.push_front(1);  // fast front insertion
    dq.push_back(5);   // fast back insertion

    for (int x : dq)
        std::cout << x << ' '; // 1 2 3 4 5
    std::cout << "\n";
}

`std::list` — Doubly Linked List

list provides O(1) insertion and erasure anywhere given an iterator, and bidirectional traversal. It does not support random access.

#include <list>
#include <iostream>

int main()
{
    std::list<int> lst = {1, 2, 4, 5};

    // Insert 3 before the element with value 4
    auto it = std::find(lst.begin(), lst.end(), 4);
    lst.insert(it, 3);

    for (int x : lst)
        std::cout << x << ' '; // 1 2 3 4 5
    std::cout << "\n";
}

`std::forward_list` — Singly Linked List

forward_list is the forward-iteration-only version of list. It has a smaller memory footprint and slightly faster insertions after a given position, but supports only forward iterators.

Associative Containers

Ordered associative containers store elements sorted by key using operator< by default. Lookup, insertion, and removal are all O(log n).

`std::map` — Key/Value Dictionary

map stores unique key/value pairs sorted by key. Access by key with [] or .at(). C++20 adds .contains().

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

int main()
{
    std::map<std::string, int> wordCount;

    // Insert via operator[]  (creates entry if absent)
    std::string words[] = {"apple", "banana", "apple", "cherry", "banana", "apple"};
    for (const auto& w : words)
        wordCount[w]++;

    // Iterate in sorted key order
    for (const auto& [word, count] : wordCount) // C++17 structured binding
        std::cout << word << ": " << count << "\n";

    // Lookup
    if (auto it = wordCount.find("banana"); it != wordCount.end())
        std::cout << "banana count: " << it->second << "\n";

    // C++20: contains()
    if (wordCount.contains("cherry"))
        std::cout << "cherry is present\n";

    // Erase by key
    wordCount.erase("cherry");
    std::cout << "size after erase: " << wordCount.size() << "\n";
}

Use map::at(key) instead of map::operator[](key) when you don’t want to inadvertently insert a default-constructed value. at() throws std::out_of_range if the key is absent.

`std::set` — Unique Sorted Elements

set stores unique elements in ascending order. It is effectively a map where the value and the key are the same element.

#include <set>
#include <iostream>

int main()
{
    std::set<int> s = {5, 3, 1, 4, 2, 3, 1}; // duplicates ignored
    for (int x : s)
        std::cout << x << ' '; // 1 2 3 4 5
    std::cout << "\n";

    s.insert(6);
    std::cout << "count(3): " << s.count(3) << "\n"; // 1 (unique)
}

`std::multimap` and `std::multiset`

multimap allows multiple values per key; multiset allows duplicate elements. Both remain sorted.

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

int main()
{
    std::multimap<std::string, int> scores;
    scores.insert({"Alice", 90});
    scores.insert({"Alice", 85});
    scores.insert({"Bob",   78});

    auto [first, last] = scores.equal_range("Alice");
    for (auto it = first; it != last; ++it)
        std::cout << "Alice: " << it->second << "\n"; // 90, then 85
}

Heterogeneous Lookup (C++14)

Ordered associative containers support heterogeneous lookup when you specify std::less<> (the “diamond functor”) as the comparator. This avoids constructing a full key object for lookup:

#include <set>
#include <string>
#include <iostream>

int main()
{
    // std::less<> enables lookup with string_view or const char*
    std::set<std::string, std::less<>> names = {"Alice", "Bob", "Charlie"};

    // No temporary std::string created for the lookup
    if (names.contains("Bob"))
        std::cout << "Found Bob\n";
}

Unordered (Hash) Containers

Unordered containers use a hash table internally. Average-case lookup, insertion, and removal are O(1) — better than ordered containers for large datasets — but worst-case is O(n) and iteration order is unspecified.

`std::unordered_map`

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

int main()
{
    std::unordered_map<std::string, double> prices;
    prices["apple"]  = 0.99;
    prices["banana"] = 0.59;
    prices["cherry"] = 2.49;

    // Average O(1) lookup
    if (auto it = prices.find("banana"); it != prices.end())
        std::cout << "banana: $" << it->second << "\n";

    // Bucket information
    std::cout << "buckets: " << prices.bucket_count() << "\n";
    std::cout << "load factor: " << prices.load_factor() << "\n";

    // Reserve to pre-size the hash table and reduce rehashing
    prices.reserve(100);
}

`std::unordered_set`

#include <unordered_set>
#include <string>
#include <iostream>

int main()
{
    std::unordered_set<std::string> visited;
    visited.insert("page1");
    visited.insert("page2");
    visited.insert("page1"); // ignored — already present

    std::cout << "unique pages: " << visited.size() << "\n"; // 2
}

To use a custom type as an unordered_map key you must provide a hash function (specialize std::hash<T> or supply a custom hasher) and an equality comparator. Forgetting either leads to a compile error.

Container Adapters

Container adapters wrap a sequence container and restrict its interface to model a specific abstract data type. They do not support iterators and cannot be used directly with standard algorithms.

stack (LIFO)
queue (FIFO)
priority_queue (max-heap)

#include <stack>
#include <iostream>

int main()
{
    std::stack<int> stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);

    while (!stk.empty()) {
        std::cout << stk.top() << ' '; // 3 2 1
        stk.pop();
    }
}

#include <queue>
#include <iostream>

int main()
{
    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();
    }
}

#include <queue>
#include <iostream>

int main()
{
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);

    while (!pq.empty()) {
        std::cout << pq.top() << ' '; // 5 4 3 1 1
        pq.pop();
    }
}

Common Member Functions

Most containers share a consistent interface for common operations:

Operation	Member	Notes
Number of elements	`size()`	O(1) for all containers
Check if empty	`empty()`	Prefer over `size() == 0`
Remove all elements	`clear()`	Does not release capacity in `vector`
Add at end	`push_back(val)`	Sequence containers
Construct at end	`emplace_back(args…)`	Avoids a copy/move
Add at front	`push_front(val)`	`deque`, `list`, `forward_list`
Insert at position	`insert(it, val)`	Returns iterator to inserted element
Remove at position	`erase(it)`	Returns iterator to next element
Find by key	`find(key)`	Associative/unordered containers
Swap two containers	`swap(other)`	O(1) for all containers
Access by key	`at(key)` / `operator[]`	`map`, `unordered_map`

Iterators

Iterators are the bridge between containers and algorithms. Every container defines its own iterator types, but they all share a common interface.

#include <vector>
#include <iostream>

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

    // Classic iterator loop
    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << *it << ' ';
    std::cout << "\n";

    // Const iteration (read-only)
    for (auto it = v.cbegin(); it != v.cend(); ++it)
        std::cout << *it << ' ';
    std::cout << "\n";

    // Reverse iteration
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        std::cout << *it << ' '; // 50 40 30 20 10
    std::cout << "\n";
}

Choosing the Right Container

Need fast random access?

Use std::vector or std::array. Both offer O(1) index access. Prefer array when the size is fixed at compile time.

Need fast insertion/deletion anywhere?

Use std::list (doubly linked, O(1) anywhere given an iterator) or std::forward_list (singly linked, lower overhead, forward-only).

Need fast key-based lookup?

Use std::unordered_map or std::unordered_set for O(1) average-case hash lookup. Use std::map or std::set when sorted order or range queries (lower_bound, upper_bound) matter.

Need fast insertion/deletion at both ends?

Use std::deque. It is faster than vector for front insertions and avoids element shifting.

Need LIFO, FIFO, or priority access?

Use the adapters std::stack, std::queue, or std::priority_queue respectively.

C++ Language

C Language

Standard Library

Preprocessor

C++ Standard Library Containers — Complete Guide

Container Categories

Sequence Containers

Associative Containers

Unordered Containers

Sequence Containers

`std::vector` — Dynamic Array

`std::array` — Fixed-Size Array

`std::deque` — Double-Ended Queue

`std::list` — Doubly Linked List

`std::forward_list` — Singly Linked List

Associative Containers

`std::map` — Key/Value Dictionary

`std::set` — Unique Sorted Elements

`std::multimap` and `std::multiset`

Heterogeneous Lookup (C++14)

Unordered (Hash) Containers

`std::unordered_map`

`std::unordered_set`

Container Adapters

Common Member Functions

Iterators

Choosing the Right Container

See Also

Build docs developers (and LLMs) love

C++ Language

C Language

Standard Library

Preprocessor

Documentation Index

​Container Categories

Sequence Containers

Associative Containers

Unordered Containers

​Sequence Containers

​std::vector — Dynamic Array

​std::array — Fixed-Size Array

​std::deque — Double-Ended Queue

​std::list — Doubly Linked List

​std::forward_list — Singly Linked List

​Associative Containers

​std::map — Key/Value Dictionary

​std::set — Unique Sorted Elements

​std::multimap and std::multiset

​Heterogeneous Lookup (C++14)

​Unordered (Hash) Containers

​std::unordered_map

​std::unordered_set

​Container Adapters

​Common Member Functions

​Iterators

​Choosing the Right Container

​See Also

Build docs developers (and LLMs) love

Container Categories

Sequence Containers

`std::vector` — Dynamic Array

`std::array` — Fixed-Size Array

`std::deque` — Double-Ended Queue

`std::list` — Doubly Linked List

`std::forward_list` — Singly Linked List

Associative Containers

`std::map` — Key/Value Dictionary

`std::set` — Unique Sorted Elements

`std::multimap` and `std::multiset`

Heterogeneous Lookup (C++14)

Unordered (Hash) Containers

`std::unordered_map`

`std::unordered_set`

Container Adapters

Common Member Functions

Iterators

Choosing the Right Container

See Also