5
\$\begingroup\$

I'm implementing a MinMaxStack<T> in C++20 that tracks minimum and maximum values. The class needs T to support <, >, and == operators. Could you please do a code review for this?

I have two questions regarding requires in the code:

  1. I'm unsure whether to use a standard concept or to define a custom concept with minimal requirements. If you have better/simpler ideas please let me know.

  2. Is requires std::constructible_from<T, U> accurate for the method push()?

Live demo

Option 1: Standard concept on class

#include <concepts>
#include <stack>

template <typename T>
    requires std::totally_ordered<T>
class MinMaxStack {
public:
    using Stack = std::stack<T>;
    using size_type = typename Stack::size_type;
    using value_type = T;

    template <typename U>
        requires std::constructible_from<T, U>
    void push(U&& value) {
        T v{std::forward<U>(value)};
        
        const bool isNewMin = m_mins.empty() || v <= m_mins.top();
        const bool isNewMax = m_maxs.empty() || v >= m_maxs.top();
        
        m_data.push(std::move(v));
        
        if (isNewMin) m_mins.push(m_data.top());
        if (isNewMax) m_maxs.push(m_data.top());
    }

    void pop() {
        if (empty()) {
            return;
        }
        
        const auto& top = m_data.top();
        const bool isMin = (top == m_mins.top());
        const bool isMax = (top == m_maxs.top());
        
        m_data.pop();
        
        if (isMin) m_mins.pop();
        if (isMax) m_maxs.pop();
    }

    [[nodiscard]] const T* top() const noexcept {
        if (empty()) {
            return nullptr;
        }
        return &m_data.top();
    }

    [[nodiscard]] const T* getMin() const noexcept {
        if (empty()) {
            return nullptr;
        }
        return &m_mins.top();
    }

    [[nodiscard]] const T* getMax() const noexcept {
        if (empty()) {
            return nullptr;
        }
        return &m_maxs.top();
    }

    [[nodiscard]] size_type size() const noexcept {
        return m_data.size();
    }

    [[nodiscard]] bool empty() const noexcept {
        return m_data.empty();
    }

private:
    Stack m_data;
    Stack m_mins;
    Stack m_maxs;
};
  

Option 2: Custom minimal concept

#include <concepts>
#include <stack>

template <typename T>
concept MinMaxComparable = requires(const T& a, const T& b) {
    { a < b }  -> std::convertible_to<bool>;
    { a > b }  -> std::convertible_to<bool>;
    { a == b } -> std::convertible_to<bool>;
};

template <typename T>
    requires MinMaxComparable<T>
class MinMaxStack {
public:
    template <typename U>
        requires std::constructible_from<T, U>
    void push(U&& value);
    
    // ... same implementation
};
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

The choice of data representation means that we have up to three copies of each element. For large T, that could be problematic. For uncopyable T, it's a show-stopper.

An alternative implementation uses std::stack<T, std::list<T>> instead of std::stack<T, std::deque<T>> for m_data; this won't invalidate any relevant iterators when we push or pop, thus allowing m_mins and m_maxs to contain iterators (or references, or pointers) to the objects in the main stack.

Orthogonal to this, consider using a single stack of { value, min, max } rather than three parallel containers.


The empty() test in pop() is a departure from the standard library stack interface, which doesn't impose this overhead on users. I guess that's an implementation choice, but it is somewhat surprising.

The functions which return pointers could instead return references if we remove the empty() tests in them.


Instead of writing template <typename T> requires std::totally_ordered<T>, we could use the shorter and (IMO) clearer abbreviated constraint:

template <std::totally_ordered T>

Consider providing an emplace() member function, like std::stack. (If we use std::list and references, this allows the use of more exotic T that need not be movable).


The main difference between MinMaxComparable and std::totally_ordered is that the former doesn't require the two operators we actually use (<= and >=). Use the standard concept, which does include those operators and which is well-known, rather than introducing more cognitive load.


As always, self-contained code such as this should be accompanied by unit tests when presented for review. That helps users to understand the supported use-cases, gives confidence that the code works as advertised, and supports experimentation with alternative implementations.

\$\endgroup\$
1
  • \$\begingroup\$ Yes, I should have said potentially three copies. Improved the wording there. \$\endgroup\$ Commented 6 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.