Implement a simplified `std::vector<T>` from scratch in C++ — a dynamically growing array template. This is a classic C++ interview question at quantitative trading firms (asked frequently in C++ developer loops at top buy-side shops), and the interviewer is testing far more than the well-known "double the capacity" trick. A strong candidate is expected to demonstrate command of raw memory allocation vs. object construction, exception safety guarantees, and the use of type traits to optimize the implementation. Your `Vector<T>` should support at minimum: - Default construction, destruction - Copy construction/assignment and move construction/assignment (the rule of five) - `push_back` (and ideally `emplace_back`) with amortized $O(1)$ growth - `operator[]`, `size()`, `capacity()`, and `reserve()` You do not need iterators, `insert`/`erase`, or a custom allocator template parameter — but you must handle element type `T` correctly: `T` may be expensive to copy, may be move-only, may throw from its copy constructor, and may have a non-trivial destructor. ### Constraints & Assumptions - Target C++17 or later; you may use `<new>`, `<memory>`, `<type_traits>`, and `<utility>`, but not `std::vector` or any other STL container for the underlying storage. - `T` is any object type: it need not be default-constructible, and its copy constructor may throw. Move-only types (e.g. `std::unique_ptr<U>`) should work. - `push_back` must be amortized $O(1)$; be prepared to justify your growth factor. - Single-threaded use; no thread-safety requirements. - Using the global `::operator new` / `::operator delete` for storage is acceptable (no allocator parameter required), but allocating storage must be separated from constructing elements. ### Clarifying Questions to Ask - Which subset of the `std::vector` API is in scope — just `push_back`/`operator[]`/`size`, or also `insert`, `erase`, and iterators? - What exception-safety guarantee should `push_back` provide — basic or strong (i.e., if an element's constructor throws mid-reallocation, is the vector left unchanged)? - Must the container support move-only element types, and types that are not default-constructible? - Is the global heap acceptable for storage, or do you want a pluggable allocator (`std::allocator_traits`-style)? - Which C++ standard may I target? (This affects `if constexpr`, `std::move_if_noexcept`, `std::construct_at`, aligned `operator new`, etc.) ### Part 1 Sketch the data layout of `Vector<T>` and implement `size()`, `capacity()`, `operator[]`, and the non-reallocating fast path of `push_back`. Then explain your growth policy when capacity is exhausted: what factor do you grow by, and why does that make `push_back` amortized $O(1)$? ```hint Layout Three members are enough: a pointer to the start of the storage plus a size and a capacity (the standard library typically stores three pointers — `begin`, `end`, `end-of-capacity` — which is equivalent). Size counts *constructed* elements; capacity counts *allocated slots*. ``` ```hint Why geometric growth If each reallocation multiplies capacity by a constant factor $g > 1$, the total number of element moves over $n$ insertions forms a geometric series bounded by a constant times $n$. Growing by a fixed *increment* instead makes `push_back` amortized $O(n)$. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2 Now implement the memory management. Why is `new T[capacity]` the wrong way to allocate the buffer? Show how you allocate raw storage, construct elements into it, and destroy/deallocate correctly in the destructor — and implement the rule of five (copy constructor, move constructor, copy assignment, move assignment, destructor). ```hint What new T[n] would force `new T[n]` *constructs* `n` objects immediately — it requires `T` to be default-constructible and makes every slot's lifetime begin at allocation, so "capacity" and "size" can no longer differ. You need storage whose slots hold no objects until you explicitly create them. ``` ```hint The right primitives Allocate uninitialized bytes with `::operator new` (mind alignment for over-aligned `T`), create objects with placement new (or `std::construct_at`), and end their lifetimes with explicit destructor calls — in reverse order of construction — before `::operator delete`. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 3 Make `push_back` exception safe. Suppose `T`'s copy constructor can throw: what happens if it throws in the middle of relocating elements to a bigger buffer? Specify the guarantee your `push_back` provides and implement the reallocation path accordingly. When is it safe to *move* elements to the new buffer instead of copying them? ```hint Guarantee taxonomy Recall the three levels: basic (invariants hold, no leaks), strong (operation succeeds or the container is left exactly as it was), and nothrow. `std::vector::push_back` gives the strong guarantee — aim for that. ``` ```hint Order of operations Do all throwing work into the *new* buffer before touching the old one: construct the new element first, then relocate the old elements, and only then destroy the old buffer and swap pointers. If anything throws, destroy what you built in the new buffer, free it, and rethrow — the old state is untouched. ``` ```hint Move vs. copy Moving an old element out of the old buffer *mutates* it — if a later move throws, you cannot restore the original state. There is a standard utility that yields an rvalue only when `T`'s move constructor is `noexcept` (or `T` is not copyable), and an lvalue otherwise. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 4 Use type traits to optimize your implementation. Which traits let you (a) relocate the buffer with `memcpy` instead of element-by-element construction, (b) skip destructor calls entirely, and (c) decide between moving and copying during reallocation? Show where each applies in your code. ```hint The three traits One trait tells you a type can be byte-copied to a new location, one tells you its destructor does nothing, and one tells you its move constructor cannot throw. Pair each with `if constexpr` so the slow path is not even instantiated. ``` #### 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 - How would you extend this to `insert` and `erase` in the middle, and what iterator/reference-invalidation rules fall out of your reallocation strategy? - How would you generalize the class to take an `Allocator` template parameter correctly, using `std::allocator_traits`? What changes in the move-assignment operator (think `propagate_on_container_move_assignment`)? - Why does `std::vector` not use a small-buffer optimization (as `std::string` typically does)? What would SBO break in your move constructor and invalidation guarantees? - Your Part 4 fast path uses `memcpy` on trivially copyable types. What does "trivially relocatable" mean, why isn't it in the standard type-trait set (as of C++17/20), and how do libraries like Folly's `fbvector` exploit it?