Hello everyone! I’ve long wanted to put together a post about the data structures available in C++ and briefly describe the advantages of each of them. In the first iteration of this article, we’ll start with those that are included in the standard STL library.
Let’s begin with the fact that a data structure is a formal way of organizing and storing information in a computer’s memory, which determines how data is arranged, how it is accessed, and which operations on it can be performed most efficiently. The choice of a data structure directly determines the performance of a program. If an operation is executed millions of times per second, even a small difference in insertion or access time can become decisive.
The C++ Standard Library (STL) provides a wide range of data structures, each solving a specific class of problems: from linear storage of elements to associative structures with key-based lookup. In this article, we will briefly review the main containers, their internal organization, and typical usage scenarios.
---
General Classification of STL Containers
Categories
Sequential: vector, deque, list, forward_list, array — elements are ordered by position.
Associative: set, map, multiset, multimap — store keys in sorted order (trees).
Unordered: unordered_set, unordered_map, unordered_multiset, unordered_multimap — based on hash tables.
Adapters: stack, queue, priority_queue — use other containers as their underlying storage.
---
Sequential Containers
1) std::vector — a dynamic array with contiguous memory storage.
std::vector<int> vec {1, 2, 3};
vec.push_back(4);
vec.emplace_back(5);
Internal structure:
The container maintains three pointers: to the beginning of the array, to the end of the filled portion, and to the end of the allocated memory (capacity). When the current capacity is exhausted, the next push_back triggers a reallocation—a new memory block is allocated, usually increased by 1.5–2 times, and all elements are copied or moved into it.
Complexity:
push_back(): O(1) amortized, O(1) during reallocation
insert()/erase() in the middle: O(1), O(1)
Access by index (operator[]): O(1), O(1)
pop_back(): O(1), O(1)
Features:
During reallocation all iterators, pointers, and references to elements become invalid. Contiguous memory layout is guaranteed (&v[0] is a pointer to the memory block). Excellent cache locality: sequential iteration is maximally efficient. Best used when fast index access and frequent appends are required, while insertions in the middle and removals at the beginning are rare.
---
2) std::deque — a double-ended queue implemented as an array of fixed-size blocks managed by a table of pointers. This allows efficient insertion and removal at both ends.
std::deque<int> d {1, 2, 3};
d.push_front(0);
d.push_back(4);
Complexity:
push_front() / push_back(): O(1), O(1)
insert() in the middle: O(1), O(1)
Access by index (operator[]): O(1), O(1)
Features:
Elements may be stored in non-contiguous memory blocks (unlike vector). Cache locality is lower than with vector. Used as the underlying container for std::queue and std::stack. Useful when insertions and removals at both ends are important while still requiring random access.
---
3) std::list — a doubly linked list where each element stores pointers to the previous and next nodes. Elements are not stored contiguously in memory, which makes insertions and deletions efficient but worsens cache locality.
std::list<int> l {1, 2, 3};
auto it = l.begin();
std::advance(it, 1);
l.insert(it, 42);
Internal structure:
Each node contains three fields: prev, next, and value. Storage is scattered in memory, and each element is allocated separately.
Complexity:
Insertion/removal by iterator: O(1)
Search by value: O(1)
Iteration: O(1)
Features:
Iterators are not invalidated during insertions/deletions (except for the removed element). There is no index access. High memory overhead due to pointers to neighbors. Used when iterator stability is important and when frequent removals in the middle occur, such as in LRU caches, task queues, and logs with deletions from the middle.
---
4) std::forward_list — a singly linked list with forward-only iteration.
std::forward_list<int> fl {1, 2, 3};
fl.push_front(0);
Internal structure:
Each element stores only a pointer to the next one. There is no size() and no bidirectional iterators. Insertion is only possible via push_front() or insert_after().
Complexity:
Insert/remove after iterator: O(1)
Search: O(1)
Iteration: O(1)
Features:
Minimal overhead (one pointer). Good for streaming or single-pass algorithms. Does not support random access and fits scenarios with limited memory and predictability (embedded systems, network pipelines).
---
5) std::array — a static array, a safe wrapper over a C-style array with an STL interface. The size is defined at compile time, and there are no dynamic allocations.
std::array<int, 3> arr {1, 2, 3};
arr[1] = 42;
Internal structure:
Elements are stored in a contiguous memory region (similar to T[N]). The size is part of the type (std::array<int, 3> and std::array<int, 4> are different types).
Complexity:
Access (operator[], at): O(1)
Iteration: O(1)
Features:
at() performs bounds checking (throws std:ut_of_range). Excellent cache locality. Used similarly to a regular static array.
---
Associative Containers (Ordered)
Associative containers are based on balanced search trees (usually red-black trees), providing ordered storage and logarithmic lookup time.
---
1) std::set — a collection of unique elements sorted by key, implemented using a balanced red-black tree.
std::set<int> s = {3, 1, 2};
s.insert(4); // add element
s.insert(2); // duplicate is ignored
Complexity:
Insertion / deletion / search: O(log n)
Iteration (in sorted order): O(1)
Features:
Elements are always sorted. Uses more memory since each element is a separate node. Applied for storing unique values with automatic sorting, implementing leaderboards, and algorithms where range queries are important (lower_bound, upper_bound).
---
2) std::map — an associative array “key → value”, implemented with a red-black tree.
std::map<std::string, int> ages = {
{"Alice", 25}, {"Bob", 30}
};
ages["Charlie"] = 28;
Complexity:
Insertion / deletion / search: O(log n)
Iteration by keys: O(1)
Features:
operator[] creates a new element if the key does not exist. Supports custom comparators. Used for associative dictionaries and indexes when a sorted key order is required.
---
Unordered Containers (Hash Tables)
Unordered containers (unordered_* family) are implemented using hash tables, where access to an element is performed via the computed hash of its key.
---
1) std::unordered_set — a collection of unique elements implemented via a hash table.
std::unordered_set<std::string> users = {"Alice", "Bob"};
users.insert("Charlie");
if (users.contains("Bob"))
std::cout << "Bob found!\n";
for (auto& u : users)
std::cout << u << " ";
Complexity:
Insertion / deletion / search: O(1)
Iteration: O(1)
Features:
Elements are not sorted. Order is unspecified. Typically used for fast membership checks.
---
2) std::unordered_map — an associative container “key → value” built on a hash table.
std::unordered_map<std::string, int> ages = {
{"Alice", 25}, {"Bob", 30}
};
ages["Charlie"] = 28;
for (auto& [name, age] : ages)
std::cout << name << ": " << age << "\n";
Complexity:
Insertion / deletion / search: O(1)
Iteration: O(1)
Features:
Element order is unspecified. Used for fast dictionaries and caches.
Uses algorithms std::make_heap, push_heap, pop_heap. Guarantees that the element with the highest priority is always first.
Operations:
push() / pop(): O(log n)
top(): O(1)
Features:
Does not provide iterators or direct access to elements. A custom comparator can be specified (for example std::greater or a user-defined one). Maintains partially ordered sets. Used for: shortest path algorithms (Dijkstra, A*), task schedulers and timers, event processing queues by priority.
---
Summary Table of STL Containers
In this article I tried to cover all containers of the C++ standard library. Below is a brief comparison of their characteristics, complexities, and areas of use.
---
Sequential Containers
Container: std::array
Main idea: Static array of fixed length.
Access: O(1)
Insertion at end: —
Insertion at beginning / middle: —
Memory / structure: Contiguous memory.
Features: No dynamic allocations.
Where to use: Small fixed structures (vectors, matrices).
---
Container: std::vector
Main idea: Dynamic array with reallocation.
Access: O(1)
Insertion at end: O(1) amortized, O(1) worst
Insertion at beginning / middle: O(1)
Memory / structure: Contiguous memory (heap).
Features: High cache locality, reallocation possible.
Where to use: Universal container, arrays, buffers.
---
Container: std::deque
Main idea: Block array (double-ended queue).
Access: O(1)
Insertion at end: O(1)
Insertion at beginning / middle: O(1) / O(1)
Memory / structure: Array of blocks in the heap.
Features: Efficient insertion at both ends.
Where to use: Queues, buffers, sliding window algorithms.
---
Container: std::list
Main idea: Doubly linked list.
Access: —
Insertion at end: O(1)
Insertion at beginning / middle: O(1)
Memory / structure: Nodes in heap (prev/next).
Features: Iterators are stable, poor cache locality.
Where to use: Frequent insertions/removals in the middle.
---
Container: std::forward_list
Main idea: Singly linked list.
Access: —
Insertion at end: O(1) (front)
Insertion at beginning / middle: —
Memory / structure: Minimal overhead.
Features: Very lightweight, forward traversal only.
Where to use: Streaming structures, low-level lists.
---
Associative Containers (Ordered)
Container: std::set
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted.
Features: Unique values.
Where to use: Ordered sets, ranking.
---
Container: std::multiset
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted.
Features: Duplicates allowed.
Where to use: Frequency tables, rankings.
---
Container: std::map
Main structure: Red-black tree (key → value).
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted by key.
Features: operator[]; stable iterators.
Where to use: Dictionaries, configuration tables.
---
Container: std::multimap
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted by key.
Features: Multiple values per key.
Where to use: Index tables, grouping.
---
Unordered Containers (Hash Tables)
Container: std::unordered_set
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Fast lookups, no sorting.
Where to use: Membership checks, filters, caches.
---
Container: std::unordered_multiset
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Supports duplicates.
Where to use: Frequency counting, unordered sets.
---
Container: std::unordered_map
Structure: Hash table (key → value).
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Key-value pairs, high speed.
Where to use: Dictionaries, routing tables, parsers.
---
Container: std::unordered_multimap
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Multiple values per key.
Where to use: Data grouping, caching.
---
Container Adapters
Container: std::stack
Underlying container: deque (by default).
Principle: LIFO.
Main operations: push, pop, top.
Complexity: O(1).
Where to use: Recursion simulation, parsers, graph traversals.
---
Container: std::queue
Underlying container: deque.
Principle: FIFO.
Main operations: push, pop, front, back.
Complexity: O(1).
Where to use: Task queues, event queues, thread processing.
---
Container: std:riority_queue
Underlying container: vector (heap).
Principle: Priority-based.
Main operations: push, pop, top.
Complexity: O(log n).
Where to use: Schedulers, Dijkstra’s algorithm.
---
Conclusion
I hope that those who previously did not dive deeply into STL now have a clearer understanding of what containers exist, how they differ, and where they are best used. I did not aim to describe the full functionality of each container—this would require more than one article. I only wanted to briefly introduce the topic and show how the main data structures are implemented so that when working with code it becomes easier to understand what happens “under the hood.” The key is understanding how they work internally, and then choosing the right option becomes obvious.
If after reading it became even a little clearer when to use vector and when map would be more appropriate—then the goal has been achieved.
---
Choosing a Container Depending on the Task
Goal: Fast random access
Best choice: std::vector
Why: Contiguous memory, O(1) access.
---
Goal: Frequent insertions in the middle
Best choice: std::list
Why: Stable iterators, O(1) insertion.
---
Goal: Queue with two ends
Best choice: std::deque
Why: Efficient insertion at both ends.
---
Goal: Fast lookup by key
Best choice: std::unordered_map
Why: Average complexity O(1).
---
Goal: Sorted data
Best choice: std::set / std::map
Why: Guaranteed ordering of elements.
---
Goal: Priority queue
Best choice: std:riority_queue
Why: The element with the highest priority is always on top.
---
Goal: Minimal overhead
Best choice: std::forward_list
Why: One pointer to the next element.
---
Goal: Small fixed arrays
Best choice: std::array
Why: No dynamic allocations.
Let’s begin with the fact that a data structure is a formal way of organizing and storing information in a computer’s memory, which determines how data is arranged, how it is accessed, and which operations on it can be performed most efficiently. The choice of a data structure directly determines the performance of a program. If an operation is executed millions of times per second, even a small difference in insertion or access time can become decisive.
The C++ Standard Library (STL) provides a wide range of data structures, each solving a specific class of problems: from linear storage of elements to associative structures with key-based lookup. In this article, we will briefly review the main containers, their internal organization, and typical usage scenarios.
---
General Classification of STL Containers
Categories
Sequential: vector, deque, list, forward_list, array — elements are ordered by position.
Associative: set, map, multiset, multimap — store keys in sorted order (trees).
Unordered: unordered_set, unordered_map, unordered_multiset, unordered_multimap — based on hash tables.
Adapters: stack, queue, priority_queue — use other containers as their underlying storage.
---
Sequential Containers
1) std::vector — a dynamic array with contiguous memory storage.
std::vector<int> vec {1, 2, 3};
vec.push_back(4);
vec.emplace_back(5);
Internal structure:
The container maintains three pointers: to the beginning of the array, to the end of the filled portion, and to the end of the allocated memory (capacity). When the current capacity is exhausted, the next push_back triggers a reallocation—a new memory block is allocated, usually increased by 1.5–2 times, and all elements are copied or moved into it.
Complexity:
push_back(): O(1) amortized, O(1) during reallocation
insert()/erase() in the middle: O(1), O(1)
Access by index (operator[]): O(1), O(1)
pop_back(): O(1), O(1)
Features:
During reallocation all iterators, pointers, and references to elements become invalid. Contiguous memory layout is guaranteed (&v[0] is a pointer to the memory block). Excellent cache locality: sequential iteration is maximally efficient. Best used when fast index access and frequent appends are required, while insertions in the middle and removals at the beginning are rare.
---
2) std::deque — a double-ended queue implemented as an array of fixed-size blocks managed by a table of pointers. This allows efficient insertion and removal at both ends.
std::deque<int> d {1, 2, 3};
d.push_front(0);
d.push_back(4);
Complexity:
push_front() / push_back(): O(1), O(1)
insert() in the middle: O(1), O(1)
Access by index (operator[]): O(1), O(1)
Features:
Elements may be stored in non-contiguous memory blocks (unlike vector). Cache locality is lower than with vector. Used as the underlying container for std::queue and std::stack. Useful when insertions and removals at both ends are important while still requiring random access.
---
3) std::list — a doubly linked list where each element stores pointers to the previous and next nodes. Elements are not stored contiguously in memory, which makes insertions and deletions efficient but worsens cache locality.
std::list<int> l {1, 2, 3};
auto it = l.begin();
std::advance(it, 1);
l.insert(it, 42);
Internal structure:
Each node contains three fields: prev, next, and value. Storage is scattered in memory, and each element is allocated separately.
Complexity:
Insertion/removal by iterator: O(1)
Search by value: O(1)
Iteration: O(1)
Features:
Iterators are not invalidated during insertions/deletions (except for the removed element). There is no index access. High memory overhead due to pointers to neighbors. Used when iterator stability is important and when frequent removals in the middle occur, such as in LRU caches, task queues, and logs with deletions from the middle.
---
4) std::forward_list — a singly linked list with forward-only iteration.
std::forward_list<int> fl {1, 2, 3};
fl.push_front(0);
Internal structure:
Each element stores only a pointer to the next one. There is no size() and no bidirectional iterators. Insertion is only possible via push_front() or insert_after().
Complexity:
Insert/remove after iterator: O(1)
Search: O(1)
Iteration: O(1)
Features:
Minimal overhead (one pointer). Good for streaming or single-pass algorithms. Does not support random access and fits scenarios with limited memory and predictability (embedded systems, network pipelines).
---
5) std::array — a static array, a safe wrapper over a C-style array with an STL interface. The size is defined at compile time, and there are no dynamic allocations.
std::array<int, 3> arr {1, 2, 3};
arr[1] = 42;
Internal structure:
Elements are stored in a contiguous memory region (similar to T[N]). The size is part of the type (std::array<int, 3> and std::array<int, 4> are different types).
Complexity:
Access (operator[], at): O(1)
Iteration: O(1)
Features:
at() performs bounds checking (throws std:ut_of_range). Excellent cache locality. Used similarly to a regular static array.
---
Associative Containers (Ordered)
Associative containers are based on balanced search trees (usually red-black trees), providing ordered storage and logarithmic lookup time.
---
1) std::set — a collection of unique elements sorted by key, implemented using a balanced red-black tree.
std::set<int> s = {3, 1, 2};
s.insert(4); // add element
s.insert(2); // duplicate is ignored
Complexity:
Insertion / deletion / search: O(log n)
Iteration (in sorted order): O(1)
Features:
Elements are always sorted. Uses more memory since each element is a separate node. Applied for storing unique values with automatic sorting, implementing leaderboards, and algorithms where range queries are important (lower_bound, upper_bound).
---
2) std::map — an associative array “key → value”, implemented with a red-black tree.
std::map<std::string, int> ages = {
{"Alice", 25}, {"Bob", 30}
};
ages["Charlie"] = 28;
Complexity:
Insertion / deletion / search: O(log n)
Iteration by keys: O(1)
Features:
operator[] creates a new element if the key does not exist. Supports custom comparators. Used for associative dictionaries and indexes when a sorted key order is required.
---
Unordered Containers (Hash Tables)
Unordered containers (unordered_* family) are implemented using hash tables, where access to an element is performed via the computed hash of its key.
---
1) std::unordered_set — a collection of unique elements implemented via a hash table.
std::unordered_set<std::string> users = {"Alice", "Bob"};
users.insert("Charlie");
if (users.contains("Bob"))
std::cout << "Bob found!\n";
for (auto& u : users)
std::cout << u << " ";
Complexity:
Insertion / deletion / search: O(1)
Iteration: O(1)
Features:
Elements are not sorted. Order is unspecified. Typically used for fast membership checks.
---
2) std::unordered_map — an associative container “key → value” built on a hash table.
std::unordered_map<std::string, int> ages = {
{"Alice", 25}, {"Bob", 30}
};
ages["Charlie"] = 28;
for (auto& [name, age] : ages)
std::cout << name << ": " << age << "\n";
Complexity:
Insertion / deletion / search: O(1)
Iteration: O(1)
Features:
Element order is unspecified. Used for fast dictionaries and caches.
Uses algorithms std::make_heap, push_heap, pop_heap. Guarantees that the element with the highest priority is always first.
Operations:
push() / pop(): O(log n)
top(): O(1)
Features:
Does not provide iterators or direct access to elements. A custom comparator can be specified (for example std::greater or a user-defined one). Maintains partially ordered sets. Used for: shortest path algorithms (Dijkstra, A*), task schedulers and timers, event processing queues by priority.
---
Summary Table of STL Containers
In this article I tried to cover all containers of the C++ standard library. Below is a brief comparison of their characteristics, complexities, and areas of use.
---
Sequential Containers
Container: std::array
Main idea: Static array of fixed length.
Access: O(1)
Insertion at end: —
Insertion at beginning / middle: —
Memory / structure: Contiguous memory.
Features: No dynamic allocations.
Where to use: Small fixed structures (vectors, matrices).
---
Container: std::vector
Main idea: Dynamic array with reallocation.
Access: O(1)
Insertion at end: O(1) amortized, O(1) worst
Insertion at beginning / middle: O(1)
Memory / structure: Contiguous memory (heap).
Features: High cache locality, reallocation possible.
Where to use: Universal container, arrays, buffers.
---
Container: std::deque
Main idea: Block array (double-ended queue).
Access: O(1)
Insertion at end: O(1)
Insertion at beginning / middle: O(1) / O(1)
Memory / structure: Array of blocks in the heap.
Features: Efficient insertion at both ends.
Where to use: Queues, buffers, sliding window algorithms.
---
Container: std::list
Main idea: Doubly linked list.
Access: —
Insertion at end: O(1)
Insertion at beginning / middle: O(1)
Memory / structure: Nodes in heap (prev/next).
Features: Iterators are stable, poor cache locality.
Where to use: Frequent insertions/removals in the middle.
---
Container: std::forward_list
Main idea: Singly linked list.
Access: —
Insertion at end: O(1) (front)
Insertion at beginning / middle: —
Memory / structure: Minimal overhead.
Features: Very lightweight, forward traversal only.
Where to use: Streaming structures, low-level lists.
---
Associative Containers (Ordered)
Container: std::set
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted.
Features: Unique values.
Where to use: Ordered sets, ranking.
---
Container: std::multiset
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted.
Features: Duplicates allowed.
Where to use: Frequency tables, rankings.
---
Container: std::map
Main structure: Red-black tree (key → value).
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted by key.
Features: operator[]; stable iterators.
Where to use: Dictionaries, configuration tables.
---
Container: std::multimap
Main structure: Red-black tree.
Access / Search: O(log n)
Insertion / Deletion: O(log n)
Ordering: Sorted by key.
Features: Multiple values per key.
Where to use: Index tables, grouping.
---
Unordered Containers (Hash Tables)
Container: std::unordered_set
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Fast lookups, no sorting.
Where to use: Membership checks, filters, caches.
---
Container: std::unordered_multiset
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Supports duplicates.
Where to use: Frequency counting, unordered sets.
---
Container: std::unordered_map
Structure: Hash table (key → value).
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Key-value pairs, high speed.
Where to use: Dictionaries, routing tables, parsers.
---
Container: std::unordered_multimap
Structure: Hash table.
Average / Worst complexity: O(1) / O(1)
Ordering: None.
Features: Multiple values per key.
Where to use: Data grouping, caching.
---
Container Adapters
Container: std::stack
Underlying container: deque (by default).
Principle: LIFO.
Main operations: push, pop, top.
Complexity: O(1).
Where to use: Recursion simulation, parsers, graph traversals.
---
Container: std::queue
Underlying container: deque.
Principle: FIFO.
Main operations: push, pop, front, back.
Complexity: O(1).
Where to use: Task queues, event queues, thread processing.
---
Container: std:riority_queue
Underlying container: vector (heap).
Principle: Priority-based.
Main operations: push, pop, top.
Complexity: O(log n).
Where to use: Schedulers, Dijkstra’s algorithm.
---
Conclusion
I hope that those who previously did not dive deeply into STL now have a clearer understanding of what containers exist, how they differ, and where they are best used. I did not aim to describe the full functionality of each container—this would require more than one article. I only wanted to briefly introduce the topic and show how the main data structures are implemented so that when working with code it becomes easier to understand what happens “under the hood.” The key is understanding how they work internally, and then choosing the right option becomes obvious.
If after reading it became even a little clearer when to use vector and when map would be more appropriate—then the goal has been achieved.
---
Choosing a Container Depending on the Task
Goal: Fast random access
Best choice: std::vector
Why: Contiguous memory, O(1) access.
---
Goal: Frequent insertions in the middle
Best choice: std::list
Why: Stable iterators, O(1) insertion.
---
Goal: Queue with two ends
Best choice: std::deque
Why: Efficient insertion at both ends.
---
Goal: Fast lookup by key
Best choice: std::unordered_map
Why: Average complexity O(1).
---
Goal: Sorted data
Best choice: std::set / std::map
Why: Guaranteed ordering of elements.
---
Goal: Priority queue
Best choice: std:riority_queue
Why: The element with the highest priority is always on top.
---
Goal: Minimal overhead
Best choice: std::forward_list
Why: One pointer to the next element.
---
Goal: Small fixed arrays
Best choice: std::array
Why: No dynamic allocations.
Last edited:
