Designing a Dynamically Sized Stack in C++23

Designing a dynamically sized stack in C++23 leverages modern language features to create a clean, efficient, and exception-safe implementation. By using `std::vector` as the underlying storage, the stack automatically grows and shrinks without manual memory management, while `std::pmr::polymorphic_allocator` (optionally combined with a monotonic buffer resource) enables allocator-aware customization in performance-critical scenarios. With C++23’s explicit object parameter (`this` as a parameter) and deduced `this`, you can write more uniform and CRTP-friendly interfaces if desired, though a simple class template remains the most practical choice for most use cases. Move semantics, perfect forwarding, and `std::optional` for the `top()` operation (returning by value) provide strong exception guarantees and zero-overhead access patterns when combined with `std::move_if_noexcept`. Ultimately, a modern dynamically sized stack in C++23 is typically just a thin, expressive adapter over `std::vector` or `std::deque`, augmented with concepts (e.g., `std::movable`) to clearly document requirements and improve error messages during template instantiation.

What “dynamically sized stack” means

A dynamically sized stack is a LIFO container whose capacity can grow (or be selected) at runtime. The abstract data type (ADT) stays the same:

• push: insert an element
• pop: remove the most recently inserted element
• top: inspect the most recently inserted element
• empty and size: query state

The design choice is how to store elements so the stack can grow safely and efficiently. In C++23, there are two common designs:

1. RAII + standard container (preferred for most code)
2. Custom node-based structure (useful as a learning exercise or for niche constraints)

Design option A (preferred): build on the standard library

In modern C++, the most practical “design” is to reuse a standard container with well-defined complexity, allocator support, and exception-safety. There are two typical approaches:

1) Use std::stack (adapter)

std::stack is a container adaptor that exposes only stack operations. By default, it uses std::deque for storage, but you can choose std::vector if you prefer contiguous memory.

#include <stack>
#include <vector>

std::stack<int> s1;                       // default underlying container: deque
std::stack<int, std::vector<int>> s2;     // vector-backed stack

2) Use std::vector directly (simple, fast, explicit)

If you want direct control over capacity and performance, a vector-backed stack is straightforward:

#include <vector>
#include <stdexcept>
#include <cstddef>

template <typename T>
class VectorStack {
public:
    VectorStack() = default;
    explicit VectorStack(std::size_t reserveCount) { data_.reserve(reserveCount); }

    void push(const T& v) { data_.push_back(v); }
    void push(T&& v) { data_.push_back(std::move(v)); }

    void pop() {
        if (data_.empty()) throw std::runtime_error("Stack is empty");
        data_.pop_back();
    }

    [[nodiscard]] T& top() {
        if (data_.empty()) throw std::runtime_error("Stack is empty");
        return data_.back();
    }

    [[nodiscard]] const T& top() const {
        if (data_.empty()) throw std::runtime_error("Stack is empty");
        return data_.back();
    }

    [[nodiscard]] bool empty() const noexcept { return data_.empty(); }
    [[nodiscard]] std::size_t size() const noexcept { return data_.size(); }

private:
    std::vector<T> data_;
};

This design is “dynamically sized” because std::vector grows automatically. It also follows the Rule of Zero: no manual new/delete, so copying/moving/destruction are correct by default.

Design option B: node-based dynamic stack (learning-focused)

A linked-list stack grows one node at a time and avoids reallocations, but it trades away cache locality and increases per-element overhead. If you implement it yourself in C++23, the key modernization is: use RAII ownership for nodes (typically std::unique_ptr), and ensure non-throwing destruction.

Below is a C++23-friendly singly-linked design. It’s simpler than a doubly linked list for a stack (you only ever touch the top):

#include <memory>
#include <stdexcept>
#include <utility>
#include <cstddef>

template <typename T>
class DynamicStack {
private:
    struct Node {
        T data;
        std::unique_ptr<Node> next;
        explicit Node(T v, std::unique_ptr<Node> n = nullptr)
            : data(std::move(v)), next(std::move(n)) {}
    };

    std::unique_ptr<Node> top_;
    std::size_t size_ = 0;

public:
    DynamicStack() = default;

    // Rule of Zero is not available here because unique_ptr prevents implicit copying.
    // For a teaching stack, we can support moves and optionally implement deep copy later.
    DynamicStack(DynamicStack&&) noexcept = default;
    DynamicStack& operator=(DynamicStack&&) noexcept = default;

    void push(const T& v) {
        top_ = std::make_unique<Node>(v, std::move(top_));
        ++size_;
    }

    void push(T&& v) {
        top_ = std::make_unique<Node>(std::move(v), std::move(top_));
        ++size_;
    }

    void pop() {
        if (!top_) throw std::runtime_error("Stack is empty");
        top_ = std::move(top_->next);
        --size_;
    }

    [[nodiscard]] T& top() {
        if (!top_) throw std::runtime_error("Stack is empty");
        return top_->data;
    }

    [[nodiscard]] const T& top() const {
        if (!top_) throw std::runtime_error("Stack is empty");
        return top_->data;
    }

    [[nodiscard]] bool empty() const noexcept { return top_ == nullptr; }
    [[nodiscard]] std::size_t size() const noexcept { return size_; }
};

Why this is “more correct” than the legacy raw-pointer version

• No manual delete: nodes are freed automatically when top_ is destroyed or reassigned.
• Destructor is noexcept by construction: it doesn’t call pop(), so it won’t throw.
• Design is simpler for a stack: a doubly linked list adds pointers you don’t need (you never remove from the middle).

Choosing a design: practical guidance

• Use std::stack / vector-backed stack for production code unless you have a strong reason not to.
• Use node-based design to teach ownership, dynamic allocation, and invariants—then modernize it with RAII.
• Copy/move policy matters: if your stack owns memory, decide whether it is copyable (deep copy) or move-only, and document it.

Small C++23 “API polish” checklist

• Prefer nullptr over NULL.
• Use [[nodiscard]] for query functions like empty() and size().
• Make functions noexcept when they truly cannot throw.
• Return references from top() to avoid unnecessary copies.
• Prefer RAII containers and smart pointers over raw owning pointers.

Quick usage example

#include <iostream>

int main() {
    VectorStack<int> s;
    s.push(10);
    s.push(20);

    std::cout << "Top: " << s.top() << "\n";
    s.pop();
    std::cout << "Size: " << s.size() << "\n";
}