Katkat

Implement a Simplified std::vector with Manual Memory Management

SIG (Susquehanna)Software Engineer · Onsite

Last 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:

  1. Memory Management: Allocate raw bytes using ::operator new (or std::allocator_traits) and free them with ::operator delete. Construct objects in-place using placement new (new (ptr) T(...)), and destroy them explicitly via ptr->~T().
  2. Geometric Growth: When capacity is exceeded during an insertion, double the capacity (start with capacity 1 if current capacity is 0).
  3. Rule of Five: Implement the destructor, copy constructor, copy assignment operator, move constructor, and move assignment operator correctly.
  4. Operations:
    • void push_back(const T& value) and void 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 least new_cap. If new_cap <= capacity(), do nothing.
    • T& operator[](size_t index) and const T& operator[](size_t index) const: Direct element access.
    • size_t size() const and size_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`)?