Skip to content

Dynamic Arrays (std::vector)

In C++, std::vector is the default dynamic array: contiguous storage, \(O(1)\) random access, size that grows as you append.

Core operations

Operation Typical complexity
push_back Amortized \(O(1)\)
pop_back \(O(1)\)
operator[] / at \(O(1)\)
insert / erase in middle \(O(n)\)
reserve(n) Preallocates capacity without changing size()

Competitive programming habits

  • Call reserve when the final size is known to avoid repeated reallocations.
  • Prefer emplace_back when constructing in place.
  • Use vector<bool> carefully (proxy reference); for bitsets use std::bitset or manual masks.