ProblemsSTL MasteryImplement a dynamic array
IntermediateSTL Mastery

Implement a dynamic array

Context

The question asked in every other C++ interview, because the interviewer was once asked it too: 'implement a dynamic array'. They won't be watching whether push_back works — they'll be watching what happens on copy and whether you call destructors. A little part of them dies every time a candidate reaches for realloc.

Task

Implement Vector<T> — a growable array like std::vector, with amortised O(1) push_back via geometric capacity growth.

Constraints

  • push_back appends; capacity must grow geometrically (e.g. double)
  • size() is the element count, capacity() the allocated slots
  • operator[] gives read/write access
  • No memory leaks; free storage in the destructor
  • Tests do not copy the Vector — focus on growth and access

Before you code

  • Why double the capacity instead of growing by one each time?
  • What is amortised complexity, and why is push_back O(1) amortised?
  • What must the destructor clean up?

Tests

  • #1push_back and indexing work
  • #2Capacity grows geometrically
  • #3Stores many elements correctly

Hints

Hint 1

When size == capacity, allocate a new array of capacity * 2 (or 1 if empty) and copy elements over.

Hint 2

Doubling keeps push_back amortised O(1); growing by one would be O(n²) total.

Editorimplement-vector.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.