std::vector
Explanation
Dynamic array. The default container, use this unless we have a specific reason not to.
See std::vector.
Memory: control block on stack, elements in heap (contiguous).
Time complexity:
| Operation | Complexity |
|---|---|
[], at() | O(1) |
front(), back() | O(1) |
size(),empty() | O(1) |
push_back(), pop_back() | O(1) amortized |
insert()/erase() | O(n) (must shift elements) |
reserve()/resize() | O(n) |
Amortized means it is not truly constant. When the array is full, it needs to allocate a new, larger block of memory and copy everything over. Some implementations might also shrink the array, therefore pop_back() is marked as amortized as well.
Use case
- Default choice for sequences.
- Size not known at compile time.
- Need fast random access.
Code
#include <print>
#include <vector>
int main() {
std::vector<uint32_t> instructions;
// Reserve to avoid reallocations.
instructions.reserve(100);
// $ echo "bl #0x40" | llvm-mc -triple=aarch64 -show-encoding
// bl #64 // encoding: [0x10,0x00,0x00,0x94]
instructions.push_back(0x94000010);
instructions.push_back(0x94000010);
instructions.push_back(0x94000010);
std::println("Size: {}, capacity: {}", instructions.size(),
instructions.capacity());
return 0;
}
Output
$ ./src/data-structures/build/std-vector
Size: 3, capacity: 100