std::list
Explanation
Doubly-linked list. Each element in its own heap allocation.
See std::list.
Memory: each node contains element + two pointers (prev/next). High memory overhead.
Time complexity:
| Operation | Complexity |
|---|---|
front(), back() | O(1) |
size(),empty() | O(1) |
push_back(), pop_back() | O(1) |
insert()/erase() | O(1) (with iterator) |
splice() | O(1) |
sort() | O(n log n) |
“With iterator” means we already have an iterator to the position where we want to insert/erase.
If sort() uses merge sort (like libstdc++ does), then the time complexity is O(n log n).
Use case
- Frequent insertion/removal in the middle (with iterator).
- Need stable iterator after modification.
std::listis rather rarely used.std::vectoris usually faster due to cache locality.
Code
#include <list>
#include <print>
int main() {
std::list<uint64_t> breakpoints = {0x1000, 0x2000, 0x3000};
auto it = std::next(breakpoints.begin());
breakpoints.insert(it, 0x1500);
for (const auto &br : breakpoints) {
std::println("{:#x}", br);
}
return 0;
}
Output
$ ./src/data-structures/build/std-list
0x1000
0x1500
0x2000
0x3000