vector - Dynamic Array & Performance Characteristics
`std::vector<T>` is the most important STL container - a **heap-allocated, contiguous, dynamically-resized array**. Elements are stored in contiguous memory, giving O(1) random access and excellent cache performance. `push_back` is amortised O(1) - the vector doubles its capacity when it runs out of space. Understanding the difference between `size` (elements) and `capacity` (allocated space) is essential for writing high-performance C++.
vector - Size/Capacity, emplace_back & Performance Idioms
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
struct Point { double x, y; };
int main() {
// ── Construction ──────────────────────────────────────────
std::vector<int> v1; // empty
std::vector<int> v2(5, 0); // [0,0,0,0,0]
std::vector<int> v3{1, 2, 3, 4, 5}; // initialiser list
std::vector<int> v4(v3.begin(), v3.end()); // from iterators
// ── size vs capacity ──────────────────────────────────────
std::vector<int> v;
v.reserve(100); // pre-allocate 100 slots - no reallocation during push
std::cout << "size=" << v.size() << " cap=" << v.capacity() << "
"; // 0 100
for (int i = 0; i < 10; ++i) v.push_back(i);
std::cout << "size=" << v.size() << " cap=" << v.capacity() << "
"; // 10 100
v.shrink_to_fit(); // release excess capacity (hint to implementation)
std::cout << "after shrink size=" << v.size()
<< " cap=" << v.capacity() << "
"; // 10 10
// ── push_back vs emplace_back ────────────────────────────
std::vector<Point> points;
points.push_back({1.0, 2.0}); // constructs Point then copies/moves
points.emplace_back(3.0, 4.0); // constructs Point directly in-place (faster)
// ── Element access ────────────────────────────────────────
std::vector<int> w{10, 20, 30, 40, 50};
std::cout << w[2] << "
"; // 30 (no bounds check - UB on OOB)
std::cout << w.at(2) << "
"; // 30 (throws std::out_of_range on OOB)
std::cout << w.front() << "
"; // 10
std::cout << w.back() << "
"; // 50
int* raw = w.data(); // direct pointer to contiguous storage
// ── Modifiers ─────────────────────────────────────────────
w.push_back(60);
w.pop_back();
w.insert(w.begin() + 2, 99); // insert at index 2 - O(n)!
w.erase(w.begin() + 2); // erase at index 2 - O(n)!
w.clear(); // size=0, capacity unchanged
// ── Erase-remove idiom ────────────────────────────────────
std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8};
// Remove all even numbers
nums.erase(
std::remove_if(nums.begin(), nums.end(),
[](int n){ return n % 2 == 0; }),
nums.end()
);
for (int n : nums) std::cout << n << " ";
std::cout << "
"; // 1 3 5 7
// ── Capacity growth demo ──────────────────────────────────
std::vector<int> growth;
size_t prev_cap = 0;
for (int i = 0; i < 20; ++i) {
growth.push_back(i);
if (growth.capacity() != prev_cap) {
std::cout << "Realloc at size=" << growth.size()
<< " new cap=" << growth.capacity() << "
";
prev_cap = growth.capacity();
}
}
// Typical output: 1, 2, 4, 8, 16, 32 - doubles each time
return 0;
}Common Mistakes
- `push_back` inside a loop without `reserve` causes repeated reallocations - if you know the size in advance, call `v.reserve(n)` before the loop. This eliminates O(log n) reallocations and all the iterator/pointer invalidation they cause.
- `v[i]` vs `v.at(i)` - `operator[]` is unchecked (undefined behaviour on out-of-bounds). `at()` checks and throws `std::out_of_range`. Use `v[i]` in hot loops (benchmarked to matter) and `at()` elsewhere.
- Using `int` instead of `size_t` as loop index - `for (int i = 0; i < v.size(); ++i)` - `v.size()` returns `size_t` (unsigned). Comparing `int` with `size_t` generates a warning and can fail when `v.size() > INT_MAX`. Use `size_t` or range-based for.
Tip
Tip
Practice vector Dynamic Array Performance Characteristics in small, isolated examples before integrating into larger projects. Breaking concepts into small experiments builds genuine understanding faster than reading alone.
Contiguous memory layout, capacity growth factors, and cache performance
Practice Task
Note
Practice Task - (1) Write a working example of vector Dynamic Array Performance Characteristics from scratch without looking at notes. (2) Modify it to handle an edge case (empty input, null value, or error state). (3) Share your solution in the Priygop community for feedback.
Quick Quiz
Common Mistake
Warning
A common mistake with vector Dynamic Array Performance Characteristics is skipping edge case testing - empty inputs, null values, and unexpected data types. Always validate boundary conditions to write robust, production-ready cpp code.
Key Takeaways
- `std::vector<T>` is the most important STL container - a **heap-allocated, contiguous, dynamically-resized array**.
- `push_back` inside a loop without `reserve` causes repeated reallocations - if you know the size in advance, call `v.reserve(n)` before the loop. This eliminates O(log n) reallocations and all the iterator/pointer invalidation they cause.
- `v[i]` vs `v.at(i)` - `operator[]` is unchecked (undefined behaviour on out-of-bounds). `at()` checks and throws `std::out_of_range`. Use `v[i]` in hot loops (benchmarked to matter) and `at()` elsewhere.
- Using `int` instead of `size_t` as loop index - `for (int i = 0; i < v.size(); ++i)` - `v.size()` returns `size_t` (unsigned). Comparing `int` with `size_t` generates a warning and can fail when `v.size() > INT_MAX`. Use `size_t` or range-based for.