Arrays & Vectors

Arrays store same-type elements in contiguous memory, enabling constant-time indexing and cache-friendly traversal.

What to understand

Memory layout
Index-based access
Insertion and deletion shifts
std::array versus std::vector

Remember this

1Random access is O(1)
2Middle insertion is O(n)
3vector grows dynamically
4Contiguous storage improves locality

Detailed notes

An array maps index i to an address using base + i × element-size. This arithmetic explains O(1) random access and why all elements must have a fixed-size representation.

std::vector adds a size and capacity around a dynamic array. When capacity is exhausted it allocates a larger block and moves elements, making an individual growth operation O(n) but a sequence of appends O(1) amortised per append.

How it works

1Validate index boundaries before access.
2Shift the suffix right before middle insertion.
3Shift the suffix left after deletion.
4Reserve capacity when approximate final size is known.

Worked trace

Insert 25 at index 2

[10, 20, 30, 40]

1Increase logical size from 4 to 5.
2Shift 40 from index 3 to 4.
3Shift 30 from index 2 to 3.
4Write 25 at the opened index 2.

Result: [10, 20, 25, 30, 40] · three writes · O(n) worst case

Where it is used

Dense tables and matrices
Heap and adjacency-matrix storage
Buffers requiring fast traversal and indexing

Common mistakes

Reading or writing outside bounds
Keeping pointers or iterators across vector reallocation
Using repeated front insertion on a vector

Complexity analysis

Operation	Best	Average	Worst	Extra space
Index access	O(1)	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)	O(1)
Append to vector	O(1)	O(1) amortized	O(n)	O(1)
Middle insert/delete	O(n)	O(n)	O(n)	O(1)

C++ implementation

C++17 reference

Core vector operations

std::vector provides contiguous dynamic storage. Insertion in the middle shifts the suffix.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> values{10, 20, 30};
    values.push_back(40);                 // amortized O(1)
    values.insert(values.begin() + 1, 15); // O(n)
    values.erase(values.begin() + 2);      // O(n)

    for (int value : values) cout << value << ' ';
    cout << "\nSize: " << values.size() << '\n';
}

13 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.