Implement a simplified `Vector<T>` that mirrors the core behavior of `std::vector<T>`. The emphasis is **not** on the public API surface but on correct, low-level memory management: cleanly separating raw allocation from object construction (`::operator new` / placement `new`), an amortized-O(1) growth strategy, correct deep-copy value semantics, and cheap move semantics. You must manage the storage by hand — you may not use `std::vector`, `std::unique_ptr`, or `new T[n]` for the buffer itself. (You may use `std::move`, `std::swap`, and type traits.) ### Constraints & Assumptions - C++17, single-threaded, no `Allocator` template parameter — use global `::operator new(bytes)` / `::operator delete(ptr)` for raw memory. - `T` may be non-trivially copyable/movable, and its constructors may throw. - API to support: default constructor, `push_back(const T&)` and `push_back(T&&)`, `operator[]`, `size()`, `capacity()`, `reserve(n)`, copy constructor, copy assignment, move constructor, move assignment, destructor. - Out of scope: iterators, `insert`/`erase` in the middle, `shrink_to_fit`. `emplace_back` with perfect forwarding is a bonus, not required. - Target: `push_back` is amortized O(1). ### Clarifying Questions to Ask - Should allocation and construction be separated (reserved-but-unconstructed capacity, like the real `std::vector`), or is a simpler "construct every slot" model acceptable? - What growth factor is expected — 2x, 1.5x — and do you care about the realloc/memory-reuse tradeoff? - Must `push_back` provide the **strong** exception guarantee across a reallocation? - Is `T` guaranteed nothrow-move-constructible, or must I handle a throwing move during relocation? - Any limits on standard-library usage beyond the storage (e.g. may I use `std::move_if_noexcept`, `std::uninitialized_copy`)? ### Part 1: Memory model and capacity growth Define the data members and implement raw allocation, `reserve(n)`, and `push_back` with a geometric growth strategy. The key requirement: **acquire raw, uninitialized memory separately from constructing elements into it.** ```hint Where to start Keep exactly three members: a raw `T*` to the buffer, `size_` (number of *constructed* elements), and `capacity_` (number of *allocated* slots). The invariant is `size_ <= capacity_`; allocated is not the same as constructed. ``` ```hint Allocation vs construction Get uninitialized bytes with `::operator new(cap * sizeof(T))` and build each element in place with placement `new (raw + i) T(value)`. Never use `new T[n]` — that default-constructs every slot and forces a default constructor on `T`. ``` ```hint Growth When `size_ == capacity_`, allocate a larger buffer (`capacity_ ? 2 * capacity_ : 1`), relocate the existing elements, destroy the originals, and free the old raw buffer. Geometric growth is what makes `push_back` amortized O(1). ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2: Value and move semantics (Rule of Five) Implement the destructor, copy constructor, copy assignment, move constructor, and move assignment so that `Vector<T>` has independent deep-copy value semantics and O(1) moves. ```hint Rule of Five A type that owns a raw resource and defines *any* of {destructor, copy ctor, copy assign, move ctor, move assign} should define *all five*. The compiler-generated shallow versions copy the pointer, so two vectors free the same buffer. ``` ```hint Copy assignment Prefer copy-and-swap for a clean strong guarantee, or, if you assign member-by-member, guard against self-assignment and free the old buffer in the right order. ``` ```hint Move Steal the pointer/size/capacity from the source and null them out so the moved-from object's destructor is a harmless no-op. Mark the move operations `noexcept`. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 3: Element lifetime and exception safety Make destruction and reallocation correct when `T` can throw. Implement the destructor, and ensure `reserve`/`push_back` neither leak nor corrupt the container if an element constructor or move throws mid-reallocation. ```hint Destruction Destroy exactly the `size_` constructed elements by calling `buf[i].~T()` in a loop, then return the raw memory with `::operator delete(buf)`. Do not use `delete[]` — it was never a `new[]` array. ``` ```hint Strong guarantee On a grow, construct all elements into the NEW buffer first. Only after that fully succeeds do you destroy the old elements and swap pointers. If a copy/move throws partway, destroy whatever you already built in the new buffer, free it, and rethrow — the old buffer is left untouched. ``` ```hint Throwing moves If `T`'s move ctor is not `noexcept`, relocating with moves can wreck both buffers on a throw. Relocate with `std::move_if_noexcept` so non-nothrow-movable types are *copied* (preserving the original) instead. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - Why might 1.5x be preferred over 2x as a growth factor for a general-purpose allocator? - How would you add `emplace_back` with perfect forwarding, and what does it save compared to `push_back`? - What are the iterator/reference invalidation rules on reallocation, and how would they shape your API contract? - How would introducing an `Allocator` template parameter change where construction and destruction happen?