Vector (Easy version)

This is the easy version of Vector.

Implement the class Vector, a simplified dynamically-resizable array container.

This is a stripped-down version of std::vector. You manage raw storage manually, construct objects in-place using placement new, and destroy them with explicit destructor calls.

This problem is designed to require careful handling of:

• placement new and explicit destructor calls
• separating allocation from construction
• geometric capacity growth
• correct lifetime management for non-trivial types

---

Overview

You must implement Vector<T>, a template container that supports a minimal interface:

• push_back(value): append an element, growing capacity if needed
• pop_back(): remove the last element
• operator[](i): indexed access
• size(), capacity(), empty()
• reserve(n): ensure capacity is at least n
• clear(): destroy all elements

The vector must never use new T[n], std::vector, or any standard container as its backing store. It must allocate raw storage and construct objects in-place using placement new.

---

Required API

#include <cstddef>
#include <new>
#include <utility>

template <class T>
class Vector {
public:
    // Construction / destruction
    Vector();                                  // empty vector, no allocation
    ~Vector();                                 // destroys all elements + frees storage

    Vector(const Vector&) = delete;            // not required
    Vector& operator=(const Vector&) = delete; // not required

    // Element access
    T& operator[](std::size_t i);
    const T& operator[](std::size_t i) const;

    // Capacity
    bool empty() const noexcept;
    std::size_t size() const noexcept;
    std::size_t capacity() const noexcept;
    void reserve(std::size_t new_cap);

    // Modifiers
    void push_back(const T& value);
    void pop_back();
    void clear() noexcept;

private:
    // You decide the internal representation.
};

---

Type Requirements on T

You may assume that T:

• is default-constructible
• is copy-constructible
• has a non-throwing destructor
• has a (possibly throwing) copy constructor

You do not need to handle:

• move-only types
• types with throwing destructors
• exception safety guarantees beyond "no leaks if a constructor throws"
• alignment requirements beyond alignof(T)

---

Storage Requirements

Your vector must manage one contiguous storage region holding capacity() slots of T-sized, T-aligned memory.

• The storage must be raw bytes (not T[]).
• The start address must be aligned to alignof(T).
• Each slot must be exactly sizeof(T) bytes apart.
• Only the first size() slots contain live objects; the remaining capacity() - size() slots are uninitialized memory.

You may use any correct strategy to allocate aligned storage, e.g.:

• ::operator new(total_bytes, std::align_val_t(alignof(T)))
• std::allocator<T>::allocate

You must not use new T[n], std::vector, std::array, std::deque, or any standard container as the backing store.

---

Growth Strategy

When size() == capacity() and a new element is added, grow capacity to max(2 * capacity(), 1):

• Initial growth: 0 → 1 → 2 → 4 → 8 → 16 → ...
• reserve(n) grows to exactly n if n > capacity(), otherwise no-op.

This guarantees amortized $O(1)$ push_back.

---

Construction Semantics (Placement New)

All element construction must go through placement new in pre-allocated raw storage:

void* slot = data_ + i;
::new (slot) T(value);

All element destruction must go through explicit destructor calls:

(data_ + i)->~T();

You must not rely on array new/delete to construct or destroy elements.

---

Behavioral Requirements

push_back(value)

• Appends a copy of value to the end.
• If size() == capacity(), grows capacity first using the growth strategy above.
• After the call, size() increases by 1.
• Amortized $O(1)$.

pop_back()

• Removes the last element.
• Calling on an empty vector is undefined behavior (do not check).
• Must call the destructor of the removed element exactly once.
• Does not change capacity().
• $O(1)$.

operator[](i)

• Returns a reference to the i-th element.
• No bounds checking. Out-of-range access is undefined behavior.
• $O(1)$.

reserve(new_cap)

• If new_cap > capacity(), allocates new storage of size new_cap, moves existing elements to it, and frees the old storage.
• If new_cap <= capacity(), no-op.
• Existing elements are preserved with their values.
• $O(n)$ when reallocation occurs.

clear()

• Destroys all live elements.
• Sets size() to 0.
• Does not change capacity() or free storage.
• $O(n)$.

Destructor

• Destroys all live elements (in any order).
• Frees the backing storage.
• Must not leak memory or skip destructor calls.

---

Allocation Constraints

• push_back must not allocate when size() < capacity().
• pop_back, operator[], size, capacity, empty, clear must perform zero heap allocations.
• Allocation may occur only in: push_back (when size == capacity), reserve, the destructor (no allocation, only deallocation).

---

Lifetime Rules

• At any time, exactly the first size() slots contain live objects of type T.
• The remaining capacity() - size() slots are uninitialized raw bytes.
• The destructor must destroy all live elements and free the backing storage. No leaks.

---

Determinism

For the same sequence of calls, behavior must be deterministic. The vector must not use threads, timing, randomness, or OS-specific behavior.

---

Notes

• Single-threaded usage only.
• You may use <type_traits>, <utility>, <new>, <memory> (for std::allocator / std::launder).
• Copy and move construction/assignment of the vector itself are deleted; you do not need to implement them.
• The only required modifiers are push_back, pop_back, and clear. You do not need insert, erase, emplace_back, resize, shrink_to_fit, at, front, back, data, or iterators.

Pointer provenance consideration

When constructing objects in raw storage, use std::launder for the returned pointer where required by the standard:

void* p = data_ + i;
::new (p) T(value);
return std::launder(reinterpret_cast<T*>(p));

While modern compilers tolerate omission in many cases, it is required for correctness under strict aliasing and pointer provenance rules.

---

Examples (Informal)

Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

assert(v.size() == 3);
assert(v[0] == 1 && v[1] == 2 && v[2] == 3);

v.pop_back();
assert(v.size() == 2);

v.clear();
assert(v.size() == 0);
assert(v.capacity() >= 2);  // capacity unchanged after clear

v.reserve(100);
assert(v.capacity() >= 100);
for (int i = 0; i < 50; i++) v.push_back(i);
// no reallocation occurred during these pushes

---

Input / Output Format

The judge will compile and run your Vector<T> implementation inside a hidden harness. You do not need to write any custom input/output parsing.

---

Notes

Reserved identifiers

The grading harness disallows the use of standard library containers as backing storage. Specifically, the following identifiers are reserved and cannot appear in your submission, even as variable, member, or alias names:

• vector
• array
• deque
• list
• forward_list
• valarray This applies to both qualified (std::vector) and unqualified uses. If your submission contains any of these tokens, it will fail to compile with an error referencing DO_NOT_USE_STD_*. Choose different names for your data members (e.g., data_, buffer_, storage_) to avoid collisions.

You may freely use:

• std::allocator (recommended for allocation)
• std::launder, std::move_if_noexcept, std::move, std::forward
• <new>, <type_traits>, <utility>, <memory>, <cstddef>, <stdexcept>, though you may assume these headers have already been imported.