## Implement and Defend a Generic C++ Stack Implement a dynamically growing generic stack in C++ and then defend its object-lifetime and call-semantics choices. Do not implement it by wrapping `std::vector` or another container. Use this interface as the target: ```cpp template <class T> class Stack { public: Stack(); ~Stack(); Stack(const Stack&) = delete; Stack& operator=(const Stack&) = delete; Stack(Stack&&) noexcept; Stack& operator=(Stack&&) noexcept; void push(const T& value); void push(T&& value); template <class... Args> T& emplace(Args&&... args); void pop(); T& top(); const T& top() const; bool empty() const noexcept; std::size_t size() const noexcept; }; ``` An empty `top` or `pop` must throw `std::out_of_range`. `push`, `emplace`, `top`, `pop`, `empty`, and `size` have amortized `O(1)`, `O(1)`, `O(1)`, `O(1)`, `O(1)`, and `O(1)` time respectively; growth is occasionally `O(n)`. Stored objects must be constructed and destroyed exactly once. Calls such as `stack.push(stack.top())`, `stack.push(std::move(stack.top()))`, and `stack.emplace(stack.top())` are valid even when the insertion triggers growth. Constructor arguments that may refer to a current element must not be used after old storage is destroyed. The rvalue form may leave the previous top in a valid moved-from state, but the appended element must receive the staged value. Assume `T` is destructible and is move-constructible or copy-constructible. If growing the capacity or computing `sizeof(T) * new_capacity` would overflow `std::size_t`, throw `std::length_error` before requesting storage. ### Part 1 — Manage Raw Storage and Object Lifetimes Implement the class using separately allocated raw storage, placement construction, explicit destruction, and geometric capacity growth. Stage insertion arguments before a reallocation can invalidate them, guard all capacity arithmetic, and explain the resulting exception-safety guarantee. #### What This Part Should Cover - The distinction between allocated bytes and live `T` objects. - Construction only for indices below `size`, followed by matching destruction. - Moving or copying live elements during growth and cleaning up partial construction. - Safe self-referential `push` and `emplace` calls when the buffer is full. - Checked doubling and byte-size calculation before allocation. - Ownership transfer in move construction and move assignment. ```hint Track two counts `capacity` describes available slots; `size` describes how many `T` lifetimes have actually begun. Before replacing a full buffer, also preserve any constructor argument that points into those live slots. ``` ### Part 2 — Compare Allocation Mechanisms Compare `new T`, `malloc`, direct calls to `::operator new`, and placement new. State which operations allocate storage, which begin object lifetime, which invoke constructors, and which cleanup function must match each allocation path. #### What This Part Should Cover - Why `malloc` alone is insufficient for a general nontrivial `T`. - How a new-expression combines allocation and construction. - How `::operator new` can allocate untyped storage without constructing `T`. - Why placement new needs an explicit destructor call and does not free storage. ```hint Separate two jobs Ask independently, “Where do the bytes come from?” and “When does a `T` object begin to exist in those bytes?” ``` ### Part 3 — Defend the `top` Return Type and Lifetime Explain why the mutable and const overloads return `T&` and `const T&`, rather than `T`, `T&&`, or only one reference type. Then analyze this code: ```cpp auto& a = stack.top(); stack.pop(); std::cout << a << '\n'; ``` #### What This Part Should Cover - Mutation through a non-const stack and read-only access through a const stack. - The copy and type-requirement consequences of returning by value. - Why an lvalue stored inside the stack should not be exposed as an rvalue by ordinary `top`. - The dangling-reference and undefined-behavior consequence after `pop` ends the object's lifetime. ```hint Follow the referred object's lifetime The reference variable can remain in scope even after the object it used to designate has been destroyed. ``` ### Part 4 — Explain Function Calls and Return Values At both the C++ language level and a typical ABI level, explain where arguments and return values may live during a call. Include registers, stack storage, caller-provided return storage, references, and copy elision. Avoid claiming that one location is mandatory on every platform. #### What This Part Should Cover - The C++ abstract-machine guarantees versus implementation-specific calling conventions. - Register and stack argument passing under a concrete ABI. - Small scalar returns versus a hidden pointer for some large aggregate returns. - Returning a reference versus returning an object by value. ```hint Do not confuse language rules with one ABI C++ specifies observable behavior; the target platform's calling convention decides many physical locations. ``` ### What a Strong Answer Covers - Provides a working lifetime-correct stack rather than only describing `std::vector`. - Matches every construction with destruction and every allocation with the right deallocation. - Keeps self-referential insertion arguments alive across growth and rejects impossible capacities before arithmetic wraps. - Gives the standard mutable and const `top` overloads and identifies the dangling reference after `pop`. - Distinguishes allocation functions, new-expressions, and placement construction. - Explains call mechanics without presenting one architecture's convention as a language guarantee. ### Follow-up Questions 1. Under what type traits can growth preserve a strong exception guarantee? 2. What additional work is required to make the stack copyable? 3. Why must move assignment destroy the destination's current elements before taking ownership? 4. How could an ABI return a large object without copying it through a return-value register? 5. Which tests distinguish safe `push(stack.top())` behavior from a use-after-destruction bug during growth?