Implement a Unique Pointer and Vector

You are interviewing for a new-grad C++ software engineering role. Implement simplified versions of two common C++ standard-library abstractions, `UniquePtr<T>` and `SimpleVector<T>`, **without using `std::unique_ptr` or `std::vector` internally**. The interviewer cares as much about resource correctness (RAII, ownership, object lifetime, exception safety) as about getting the API right. Implement each abstraction as a class template, then answer the follow-up questions on copy vs. move semantics. ### Constraints & Assumptions - Target **C++11 or later** (move semantics, `noexcept`, `= delete`, placement new all available). - `T` is an arbitrary type that is move-constructible (and copy-constructible for the copy paths). Do **not** assume it is trivially copyable, trivially destructible, or default-constructible. - You may use `<new>`, `<utility>` (for `std::move`/`std::swap`), `<cstddef>`, and `<stdexcept>`. You may **not** use any standard container, smart pointer, or `std::allocator` machinery. - Allocation failures throw `std::bad_alloc`; you need not handle out-of-memory beyond not leaking. - Single-threaded; no thread-safety required. `operator[]` is unchecked like `std::vector::operator[]` unless you state otherwise. ### Clarifying Questions to Ask - Should `reset()`/`release()` follow `std::unique_ptr` semantics exactly (`reset()` deletes the current object; `release()` relinquishes without deleting)? - Does `UniquePtr` need a custom deleter or array (`T[]`) support, or only single-object ownership? - What is the expected behavior of `pop_back()` on an empty vector — undefined behavior, an exception, or a no-op? - Should `operator[]` perform bounds checking, or is out-of-range access undefined behavior like `std::vector::operator[]`? - Is exception safety (a strong guarantee on reallocation and copy) a requirement, or is the basic guarantee acceptable? - Can I assume `T`'s move constructor is `noexcept`, or should reallocation fall back to copying when it isn't? ### Part 1: Implement `UniquePtr<T>` Implement a move-only owning pointer that owns **exactly one** heap-allocated object of type `T` and deletes it in the destructor (RAII). Support: - Default construction (owns nothing), and `explicit` construction from a raw `T*`. - `get()`, `release()`, `reset()`, `operator*`, `operator->`, and `explicit operator bool`. - Deleted copy constructor and copy assignment (unique ownership cannot be duplicated). - Move construction and move assignment that transfer ownership and leave the source empty. - Safe behavior under self-move-assignment. ```hint Where the resource lives The whole type wraps a single owned pointer. The destructor's only job is to delete it — and deleting a null pointer is a safe no-op, so a default-constructed (empty) pointer needs no special case. Every other method is some careful way of swapping that one pointer in or out. ``` ```hint Why no copy, and how a move must behave If two instances held the same raw pointer, both destructors would delete it — a double-free. That invariant is what forces copy ctor / copy assign to be unavailable. A move, by contrast, must leave the source in a state where its eventual destructor does nothing — so think about what the source's pointer should be afterward. ``` ```hint Sequencing move assignment Move assignment is the subtle one: you already own a resource and are taking another. Think about three things in order — the case where source and destination are the same object, releasing what you currently own, and adopting the source's pointer while leaving it empty. Also recall how `release` and `reset` differ: one relinquishes without freeing, the other frees the current object before taking a new one. Consider which operations can be marked `noexcept`. ``` #### What This Part Should Cover - **Move-only correctness**: copy ctor and copy assign are deleted; move ctor and move assign transfer the pointer and null out the source; self-move-assignment is safe (no delete-then-read of a dangling pointer). - **RAII destructor**: `delete ptr_` reliably releases the resource and is a no-op when empty — no leaks, no double-frees, no use-after-free. - **Correct `reset`/`release` semantics**: `release()` relinquishes ownership without deleting; `reset()` deletes the currently-held object, with the old and new pointers sequenced so it never deletes the wrong one. - **API surface and `const`/`noexcept` discipline**: `explicit` raw-pointer ctor and `explicit operator bool` to block accidental conversions; `get`/`operator->`/`operator bool` marked `const`/`noexcept`; move operations `noexcept`. ### Part 2: Implement `SimpleVector<T>` Implement a dynamic array that stores elements contiguously, tracks `size()` and `capacity()` separately, and grows automatically. Support: default construction, destruction, copy construction, copy assignment, move construction, move assignment, `push_back` (both `const T&` and `T&&` overloads), `pop_back`, `operator[]` (const and non-const), `reserve`, and `clear`. Construct and destroy elements correctly; never default-construct unused capacity. ```hint Separate the bytes from the objects Because `T` might not be default-constructible, allocating an array of `T` directly won't work — it would default-construct every slot. Think about allocating untyped storage instead, sized for `cap` elements, and tracking three fields: a storage pointer, the number of live elements, and the number of allocated slots. The first live-element slots hold constructed objects; the rest are uninitialized storage. ``` ```hint Constructing and destroying in place You'll need a way to construct an object into a specific raw slot, and a way to destroy one element without freeing the buffer. C++ gives you language facilities for both (constructing an object at a known address, and invoking a destructor explicitly). `clear()` should destroy every element but keep the buffer; the destructor destroys the elements and then frees the raw storage; `pop_back` destroys one element and decrements the count. ``` ```hint Growth, reserve, and copy-assign `reserve` allocates a bigger buffer, relocates existing elements into it (prefer moving where it's safe to do so), destroys the originals, frees the old buffer, then commits the new pointer/capacity. Grow the capacity geometrically (rather than by one) so that a sequence of pushes is amortized $O(1)$. For copy *assignment*, consider an idiom that reuses your copy constructor and lets self-assignment and exception safety fall out for free. ``` ```hint When a constructor throws mid-fill If an element's copy/move constructor throws while you fill or relocate a buffer, the half-built object's own destructor will **not** run to rescue you. On both the copy path and the growth path, you must by hand destroy the elements you already constructed in the new buffer and free those raw bytes before letting the exception propagate. ``` #### What This Part Should Cover - **Placement new / explicit destruction**: raw allocation (`::operator new`) is separated from element construction (placement `new`) and destruction (explicit `~T()`); unused capacity in `[size_, capacity_)` is never default-constructed. - **Full Rule of Five, both copyable and movable**: copy = deep copy into a fresh buffer; move = $O(1)$ buffer theft that empties the source; copy-assign reuses the copy ctor (e.g. copy-and-swap) so self-assignment and exception safety follow. - **Correct reallocation and growth**: old elements relocated (moved when safe, else copied) then destroyed, old buffer freed, `size_`/`capacity_` committed; geometric growth yields amortized $O(1)$ `push_back`. - **Exception safety on the fill and growth paths**: a throwing element constructor leaks nothing — already-constructed elements in the new buffer are destroyed and the buffer freed before rethrowing; the source / old buffer stays intact (strong guarantee, aided by `std::move_if_noexcept`). - **Edge cases and accessor discipline**: empty container, `pop_back` on empty, self-assignment; `clear()` keeps the buffer; `operator[]` provided in const and non-const forms. ### What a Strong Answer Covers These dimensions span both Parts and are graded across the whole answer: - **RAII / ownership end to end**: every owned resource has exactly one owner whose destructor releases it; no leaks, no double-frees, no use-after-free in either type. - **Rule of Three/Five consistency**: each type defines (or deletes) destructor, copy ctor, copy assign, move ctor, and move assign as a coherent set — `UniquePtr` move-only, `SimpleVector` fully copyable and movable. - **`const`-correctness and `noexcept` placement**: accessors `const`; move operations and other non-throwing operations marked `noexcept`, with the reasoning for why. - **Lifetime precision**: each object is constructed and destroyed exactly once; a thrown constructor cannot leak because the partially-built container's own destructor never runs. ### Follow-up Questions 1. Explain the difference between **copy semantics** and **move semantics**, and identify exactly where each is used in your two implementations (and why `UniquePtr` is move-only while `SimpleVector` is both copyable and movable). 2. Why does `std::vector` require `T`'s move constructor to be `noexcept` to *use* moves during reallocation? What happens to the strong exception guarantee if moves can throw? 3. How would you support a **custom deleter** in `UniquePtr` without adding a runtime cost for the default `delete` case? 4. Your `push_back` may invalidate references and iterators on reallocation. Which operations invalidate them, and how does this compare to `std::vector`?