Vector (Hard Version)

This is the hard version of Vector.

Implement the class Vector, a generic dynamically-resizable array container that mirrors the core semantics of std::vector<T>.

Your implementation must correctly handle non-trivial types, provide strong exception safety where the standard requires it, and use placement new + explicit destructor calls to manage object lifetimes in raw storage.

This problem is designed to require careful handling of:

• placement new and explicit destructor calls
• std::move_if_noexcept and the move-vs-copy decision during reallocation
• strong exception safety (rollback on throw)
• perfect forwarding via emplace_back
• self-referential push_back (e.g. v.push_back(v[0]) triggering growth)
• iterator invalidation rules for insert/erase

---

Overview

You must implement Vector<T>, a template container that supports the full core interface of std::vector<T>, including:

• construction (default, sized, fill, copy, move)
• assignment (copy and move)
• element access (operator[], at, front, back, data)
• capacity management (reserve, shrink_to_fit, resize)
• modifiers (push_back, emplace_back, pop_back, insert, erase, clear)
• iteration (begin, end — raw pointer iterators are acceptable)

The vector must never use new T[n]. It must allocate raw storage and construct objects in-place using placement new.

---

Required API

#include <cstddef>
#include <cstdint>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>

template <class T>
class Vector {
public:
    // --- Construction / destruction ---
    Vector();
    explicit Vector(std::size_t count);                  // value-initialized
    Vector(std::size_t count, const T& value);           // fill
    Vector(const Vector& other);                         // copy
    Vector(Vector&& other) noexcept;                     // move
    ~Vector();

    // --- Assignment ---
    Vector& operator=(const Vector& other);              // strong guarantee
    Vector& operator=(Vector&& other) noexcept;

    // --- Element access ---
    T& operator[](std::size_t i);
    const T& operator[](std::size_t i) const;
    T& at(std::size_t i);                                // throws std::out_of_range
    const T& at(std::size_t i) const;
    T& front();             const T& front() const;
    T& back();              const T& back()  const;
    T* data() noexcept;     const T* data() const noexcept;

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

    // --- Modifiers ---
    void clear() noexcept;
    void push_back(const T& value);                      // strong guarantee
    void push_back(T&& value);                           // strong guarantee (if move is noexcept)
    template <class... Args>
    T& emplace_back(Args&&... args);                     // strong guarantee
    void pop_back();
    void resize(std::size_t count);
    void resize(std::size_t count, const T& value);

    // --- Iterators (raw pointer iterators are acceptable) ---
    T* begin() noexcept;             T* end() noexcept;
    const T* begin() const noexcept; const T* end() const noexcept;

    // --- insert / erase ---
    T* insert(const T* pos, const T& value);
    T* insert(const T* pos, T&& value);
    T* erase(const T* pos);
    T* erase(const T* first, const T* last);

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

---

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.
• shrink_to_fit() may reduce capacity to size() (this operation is non-binding in the standard, but for this problem it must shrink if size() < capacity()).

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(std::forward<Args>(args)...);

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.

---

Strong Exception Safety

The following operations must provide the strong exception safety guarantee: if any exception is thrown during the operation, the vector is left in its original state (same size(), same capacity(), same elements, same addresses where possible).

• reserve(new_cap)
• push_back(const T&), push_back(T&&)
• emplace_back(Args&&...)
• insert(pos, value)
• copy operator=

std::move_if_noexcept Requirement

When relocating elements during reallocation (e.g., during reserve or growth in push_back):

• If std::is_nothrow_move_constructible_v<T> is true, move elements to the new storage.
• Otherwise, if T is copy-constructible, copy elements (do not move).

This is required for strong exception safety: if a non-noexcept move throws partway through reallocation, the original storage may already be corrupted. Copying preserves originals so they can be restored on throw.

The standard idiom is std::move_if_noexcept(elem), which yields T&& if T's move ctor is noexcept, and const T& otherwise.

If T is neither nothrow-move-constructible nor copy-constructible (e.g., a move-only type with a throwing move), strong guarantee cannot be provided; basic guarantee is sufficient in that case.

Self-Referential push_back

The following must work correctly:

Vector<int> v;
v.push_back(1);
v.push_back(v[0]);  // capacity grows here; v[0] is a reference into about-to-be-freed storage

The naive implementation reads v[0] after allocating new storage but before moving old elements, then frees old storage — at which point v[0] was a reference into freed memory. Your implementation must construct the new element from the old reference before invalidating the old storage, or otherwise handle this case correctly.

---

Behavioral Requirements

at(i)

• Throws std::out_of_range if i >= size().
• operator[](i) does not check bounds.

pop_back()

• Calling on an empty vector is undefined behavior. Do not check.
• Must call the destructor of the removed element exactly once.

clear()

• Destroys all elements; sets size() to 0; does not change capacity().

resize(n)

• If n < size(): destroys the trailing size() - n elements.
• If n > size(): appends n - size() value-initialized elements (or copies of value for the two-argument overload). Reallocates if n > capacity().

insert(pos, value)

• Inserts value before pos; shifts subsequent elements forward by one.
• Returns a pointer to the inserted element.
• May reallocate if size() == capacity(). After reallocation, all prior iterators are invalidated.
• Must provide the strong guarantee.

erase(pos) / erase(first, last)

• Removes the element(s); shifts subsequent elements back.
• Returns a pointer to the element after the erased range (or end() if at the tail).
• Does not reallocate.

emplace_back(args...)

• Constructs a T in-place at the end using perfect forwarding.
• Must work for types that are not copy- or move-constructible but are constructible from args....

---

Complexity Requirements

• push_back, emplace_back, pop_back: amortized $O(1)$.
• operator[], at, front, back, data, size, capacity, empty: $O(1)$.
• reserve, copy ctor, copy assignment: $O(n)$.
• move ctor, move assignment: $O(1)$.
• insert(pos, value), erase(pos): $O(n)$ worst case.
• clear: $O(n)$ (destructor calls).

---

Allocation Constraints

• The vector must not allocate during operations that fit within current capacity. Specifically, push_back, emplace_back, pop_back, clear, operator[], at, etc. must perform zero heap allocations when no growth is required.
• Reallocation may occur only in: growth (push_back/emplace_back/insert when size == capacity), reserve, shrink_to_fit, resize (when growing past capacity), copy ctor/assignment, fill/sized ctor.

---

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.
• After move (ctor or assignment), the moved-from vector must be left in a valid state with size() == 0 and capacity() == 0 (storage transferred to the destination).

---

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 std::allocator<T> or raw ::operator new/::operator delete with std::align_val_t.
• You may use <type_traits>, <utility>, <new>, <stdexcept>, and <memory> (for std::allocator / std::launder / std::move_if_noexcept).
• Iterators may be raw pointers (T* and const T*).
• The design intent: this problem tests low-level lifetime management, exception safety reasoning, and the move-vs-copy decision under non-trivial generic constraints — the same skill set tested when discussing std::vector internals in HFT and systems interviews.

Pointer provenance consideration

When constructing objects in reused storage (e.g., after clear() followed by push_back), use std::launder for the returned pointer where required by the standard:

void* p = data_ + i;
::new (p) T(std::forward<Args>(args)...);
return std::launder(reinterpret_cast<T*>(p));

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

---

Examples (Informal)

Vector<std::string> v;
v.push_back("hello");
v.push_back("world");
v.emplace_back(5, '!');           // constructs std::string(5, '!') = "!!!!!"

assert(v.size() == 3);
assert(v[0] == "hello");

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

Vector<std::string> w = v;        // copy
Vector<std::string> x = std::move(v);  // move; v is now empty

// Strong exception safety:
//   if T's copy ctor throws on the Nth call during reserve(),
//   the vector must be unchanged.

// Self-referential push_back:
Vector<int> s;
s.push_back(1);
s.push_back(s[0]);                // must work even when growth is triggered

---

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.