std::deque
Explanation
Double-ended queue. Fast insertion/removal at both front and back.
See std::deque.
Memory: array of pointers to fixed-size chunks (all on heap).
Time complexity:
| Operation | Complexity |
|---|---|
[], at() | O(1) |
front(), back() | O(1) |
size(),empty() | O(1) |
push_back(), pop_back() | O(1) |
push_front(), pop_front() | O(1) |
insert()/erase() | O(n) |
Use case
- Need fast
push_front/pop_front. - Need stable references (
push/insertdo not invalidate). - Do not need contiguous memory.
Code
#include <deque>
#include <print>
int main() {
std::deque<uint64_t> addresses;
addresses.push_back(0x10001000);
addresses.push_front(0x10002000);
std::println("Front: {:#x}", addresses.front());
std::println("Back: {:#x}", addresses.back());
return 0;
}
Output
$ ./src/data-structures/build/std-deque
Front: 0x10002000
Back: 0x10001000