DataslopeArrays and std::vector
Learn fixed arrays, std::array, std::vector, contiguous memory, iteration, capacity, and matrix-style storage in C++
Arrays are the first data structure most programmers meet: a sequence of values stored side by side. In modern C++, the array you will use most is std::vector<T> because it grows dynamically while keeping fast O(1) indexing.
C-style arrays
A C-style array such as int a[5] has a fixed size known at compile time. It is compact and fast, but it loses size information easily because it decays to a pointer when passed to many functions.
You almost never want raw arrays for DSA practice because std::array and std::vector are safer and more expressive.
std::array<T, N>
std::array is a fixed-size array wrapper. It preserves the size, supports range-for loops, and behaves like a normal value object.
std::vector<T>: the workhorse
std::vector is a dynamic array. It stores elements contiguously like an array, but it can allocate a larger block and move elements when it needs more capacity.
Use operator[] when you know the index is valid. Use .at() when you want bounds checking and an exception on invalid access.
Contiguous memory layout
A vector keeps values next to each other in memory. That makes iteration cache-friendly: when the CPU loads one element, nearby elements are likely pulled into cache too.
The printed addresses should increase by sizeof(int) each time in a normal implementation.
Iteration patterns
Index-based loops are useful when you need positions. Range-for loops are clean when you only need values. Iterators are the common language of STL algorithms.
Resizing, capacity, and amortized push
size() is how many elements are currently stored. capacity() is how many elements fit before reallocation. When capacity is full, a vector usually grows by allocating a larger buffer, often about double the old capacity.
That rare reallocation is why push_back is O(1) amortized, as discussed in the complexity page.
Timing one million pushes
Browser timing is noisy, but this shows how to measure a sequence of pushes with <chrono>.
2D vectors
A matrix is often represented as std::vector<std::vector<int>>: a vector of rows, where each row is another vector.
Vector operation costs
| Operation | Complexity | Why |
|---|---|---|
v[i], v.at(i) | O(1) | Direct address calculation |
push_back | O(1) amortized | Rare reallocations are spread over many pushes |
| insert in middle | O(n) | Elements after the position shift right |
| erase from middle | O(n) | Elements after the position shift left |
Practice: reverse a vector in-place
Implement reverseInPlace without using std::reverse. Swap from both ends until the pointers meet.
Practice: second-largest value
Implement secondLargest in one pass without sorting. Keep the best value and the runner-up as you scan.
Check your understanding
Why does iterating through a std::vector<int> often run faster than iterating through a linked list with the same number of integers?
The vector stores elements contiguously, which improves cache locality.
A vector changes every operation to O(log n).
A linked list cannot store integers.
A vector never reallocates memory.
For most DSA problems, why should you usually try std::vector before std::list?
std::list has O(1) random access.
std::vector has compact storage, O(1) indexing, and excellent iteration performance.
std::vector can only store primitive types.
std::list is always asymptotically slower for every operation.
What is the main behavioral difference between v.at(i) and v[i] for a std::vector?
v.at(i) is always O(n), while v[i] is O(1).
v[i] checks bounds and throws if invalid.
v.at(i) performs bounds checking and throws an exception when i is invalid.
v.at(i) inserts a new element if i is too large.