Implement a Simplified std::vector with Manual Memory Management
SIG (Susquehanna)Software Engineer · OnsiteLast updated
Tests practical systems programming in C++, specifically decoupling raw memory allocation from object construction, managing dynamic capacity growth, and adhering to the Rule of Five.
Problem Statement
In high-performance systems, standard containers often require custom reimplementation or specialized variants to guarantee predictable latency and control over memory layout. Your task is to implement a simplified generic dynamic array, SimpleVector, that manages raw uninitialized memory directly without relying on std::vector.
A common pitfall with naive implementations is using new T[capacity], which forces all capacity elements to be default-constructed immediately. Your implementation must cleanly decouple raw memory allocation from object construction and destruction.
Implement the SimpleVector class template with the following specifications:
- Memory Management: Allocate raw bytes using
::operator new(orstd::allocator_traits) and free them with::operator delete. Construct objects in-place using placement new (new (ptr) T(...)), and destroy them explicitly viaptr->~T(). - Geometric Growth: When capacity is exceeded during an insertion, double the capacity (start with capacity 1 if current capacity is 0).
- Rule of Five: Implement the destructor, copy constructor, copy assignment operator, move constructor, and move assignment operator correctly.
- Operations:
void push_back(const T& value)andvoid push_back(T&& value): Appends an element to the end.void pop_back(): Destroys the last element and decrements size. Behavior is undefined if empty.void reserve(size_t new_cap): Expands capacity to at leastnew_cap. Ifnew_cap <= capacity(), do nothing.T& operator[](size_t index)andconst T& operator[](size_t index) const: Direct element access.size_t size() constandsize_t capacity() const.
Interface
template
class SimpleVector {
public:
SimpleVector() noexcept;
~SimpleVector();
SimpleVector(const SimpleVector& other);
SimpleVector& operator=(const SimpleVector& other);
SimpleVector(SimpleVector&& other) noexcept;
SimpleVector& operator=(SimpleVector&& other) noexcept;
void push_back(const T& value);
void push_back(T&& value);
void pop_back();
void reserve(size_t new_capacity);
T& operator[](size_t index) noexcept;
const T& operator[](size_t index) const noexcept;
size_t size() const noexcept;
size_t capacity() const noexcept;
private:
T* data_ = nullptr;
size_t size_ = 0;
size_t capacity_ = 0;
};
Example
SimpleVector vec;
vec.push_back("hello");
vec.push_back("world");
assert(vec.size() == 2);
assert(vec.capacity() == 2);
assert(vec[0] == "hello");
vec.push_back("trading");
assert(vec.size() == 3);
assert(vec.capacity() == 4); // Doubled from 2 to 4
vec.pop_back();
assert(vec.size() == 2);
assert(vec.capacity() == 4); // Capacity unchanged
Constraints & Edge Cases
- Elements in
data_[size_ ... capacity_ - 1]must remain uninitialized raw memory; do not invoke default constructors for unused slots. - Handle self-assignment safely in both copy and move assignment operators.
- Ensure exception safety during reallocation: if an element constructor throws while moving/copying elements to a new buffer, clean up any partially constructed elements in the new buffer and deallocate the new memory without leaking.
Hints
Hint 1
Use raw allocation (`static_cast(::operator new(n * sizeof(T)))`) and placement new (`new (static_cast(dst)) T(...)`) instead of `new T[n]` to prevent premature default initialization.
Hint 2
During reallocation, conditionally move elements using `std::move_if_noexcept` so that if an element's move constructor can throw, you copy instead to preserve the strong exception guarantee.
Hint 3
Ensure that destruction and deallocation are separated: iterate backwards or forwards to call `p->~T()` for valid elements before freeing the memory block with `::operator delete`.
Follow-up questions
- Why is a growth factor of 1.5 often preferred over 2.0 in production allocators regarding memory fragmentation and reuse?
- How would you implement `template void emplace_back(Args&&... args)` to construct elements directly in-place?
- How can you optimize bulk reallocation for trivially copyable types (e.g., using `std::is_trivially_copyable` and `std::memcpy`)?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.